408034: GYM102964 H Krosh and count arrays problem

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Krosh and count arrays problemtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Krosh has three integers $$$n$$$, $$$m$$$, $$$k$$$. Help him to calculate number of arrays with following properties:

1. Number of elements in the array is $$$n$$$

2. Every element of the array is integer between $$$1$$$ and $$$m$$$

3. Sum of the array is divisible by $$$k$$$.

Output amount of these arrays modulo $$$10^9+7$$$.

Input

You are given three integers $$$1 \le n \le 40000$$$, $$$1 \le m \le 100$$$, $$$m < k \le 10^9$$$.

Output

Output number of arrays which satisfy conditions in the statement modulo $$$10^9+7$$$.

ExampleInput
5 3 7
Output
20

加入题单

上一题 下一题 算法标签: