408034: GYM102964 H Krosh and count arrays problem

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$$$.

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

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

5 3 7

20