H. Krosh and count arrays problem
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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 \lt k \le 10^9$$$.

Output

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

Example
Input
5 3 7
Output
20