AT_abc208_f [ABC208F] Cumulative Sum

[problemUrl]: https://atcoder.jp/contests/abc208/tasks/abc208_f 非負整数 $ 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 $

$ f(N,\ M) $ を $ (10\ ^\ 9\ +\ 7) $ で割った余りを出力せよ。

### 制約 - $ 0\ \leq\ N\ \leq\ 10^{18} $ - $ 0\ \leq\ M\ \leq\ 30 $ - $ 1\ \leq\ K\ \leq\ 2.5\ \times\ 10^6 $ - 入力は全て整数である。 ### Sample Explanation 1 $ K\ =\ 2 $ の時、 $ n\ \leq\ 3,\ m\ \leq\ 4 $ における $ f(n,\ m) $ の値は次のようになります。 $ m\ =\ 0 $ $ m\ =\ 1 $ $ m\ =\ 2 $ $ m\ =\ 3 $ $ m\ =\ 4 $ $ n\ =\ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ n\ =\ 1 $ $ 1 $ $ 1 $ $ 1 $ $ 1 $ $ 1 $ $ n\ =\ 2 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ $ 8 $ $ n\ =\ 3 $ $ 9 $ $ 14 $ $ 20 $ $ 27 $ $ 35 $