Nightmare

Limits: 2 sec., 256 MiB

To wake up calculate : \[result = \sum_{i=1}^{p} \prod_{j=0}^{m-1} \sum_{\substack{k=1, \\ k \equiv j \bmod m}}^{n} k^{i}\]

Input

The first line contains three integers \(p\), \(m\), and \(n\).

Output

Print one integer — result modulo \(10^9+7\).

Constraints

\(1 \le p \le 10\),

\(1 \le m \le 50\),

\(1 \le n \le 10^{12}\).

Samples