{"code":"2022thtc1b4","name":"Quà kỷ niệm (THT C1 Đà Nẵng 2022)","description":"Để động viên các bạn học sinh trong lớp học VUI NHỘN nhân dịp lớp đoạt chức vô địch\r\ngiải bóng đá cấp trường vừa qua, cô Mười Ba dự định sẽ mua tặng các học sinh của mình những\r\nchiếc áo LV mới nhất.\r\n\r\nLớp học VUI NHỘN có $n$ học sinh. Cửa hàng cô dự định đến có bán $k$ màu áo khác nhau.\r\nCô Mười Ba muốn mua $n$ chiếc áo cho $n$ học sinh của mình, đồng thời cô cũng muốn với mỗi màu\r\náo từ $1$ đến $k$, sẽ có ít nhất $m$ bạn mặc chiếc áo có màu này.\r\n\r\nÔng chủ cửa hàng rất thích toán, vì vậy ông đố cô rằng có bao nhiêu cách mua áo khác nhau,\r\nsao cho cô sẽ mua $n$ chiếc áo, và với mỗi màu áo từ $1$ đến $k$ xuất hiện ít nhất $m$ lần trong $n$ chiếc áo.\r\nVì bận tính tiền nên cô không thể tập trung giải quyết bài toán, bạn hãy giúp cô giải bài này để được\r\ngiảm giá nhé.\r\n\r\n

Input

\r\n\r\n- Một dòng chứa 3 số nguyên dương $n, k, m (1 \\le k \\le n, m ∗ k \\le n \\le \r\n10^6 , 1 \\le m \\le 2)$\r\n\r\n

Output

\r\n\r\n- Số cách chia thỏa mãn yêu cầu đề bài sau khi mod $10^9 + 7$.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($10\\%$ số điểm): $n \\le 10, k \\le 5$\r\n- Subtask $2$ ($20\\%$ số điểm): $n \\le 100, k \\le 10$\r\n- Subtask $3$ ($20\\%$ số điểm): $n \\le 3000, k \\le $\r\n- Subtask $4$ ($10\\%$ số điểm): $n \\le m ∗ k + 1$\r\n- Subtask $5$ ($20\\%$ số điểm): $n \\le 10^6, k \\le 10^6, m = 1$\r\n- Subtask $6$ ($20\\%$ số điểm): $n \\le 10^6, k \\le 3000, m = 2$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 2 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 6\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Giải thích test 1: Với 3 học sinh, có 2 màu áo, các cách chọn áo cho học sinh là: 111, 112, 121, 122, 211, 212, 221, 222\r\n Có 6 cách chọn áo để mỗi màu áo xuất hiện ít nhất 1 lần\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 2 2\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 6\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Giải thích test 2: Với 4 học sinh, có 2 màu áo, các cách chọn áo cho học sinh là: 1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222, 2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222 Có 6 cách chọn áo để mỗi màu áo xuất hiện ít nhất 2 lần","points":200.0,"partial":false,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}