Для цілих невід’ємних чисел \(n\) і \(m\) визначимо функцію \(f(n, m)\) таким чином, використовуючи ціле додатне число \(K\).

• \(\displaystyle f(n, m) = \begin{cases} 0 & (n = 0) \\ n^K & (n \gt 0, m = 0) \\ f(n-1, m) + f( n, m-1) & (n \gt 0, m \gt 0) \end{cases}\)

Для даних \(N\), \(M\) та \(K\) знайдіть \(f(N, M)\) за модулем \((10 ^ 9 + 7)\).

Формат вхідних даних

Вхідний потік містить цілі числа \(N, M, K\) (\(0 \le N \le 10^{18}\), \(0 \le M \le 30\), \(1 \le K \le 2.5 \times 10^6\))

Формат вихідних даних

У вихідний потік виведіть шукане значення функції.

Примітка

До прикладу 1:

Приклад вхідних даних

3 4 2

Приклад вихідних даних

35

Приклад вхідних даних

0 1 2

Приклад вихідних даних

0

Приклад вхідних даних

1000000000000000000 30 123456

Приклад вихідних даних

297085514