No.720 行列のできるフィボナッチ数列道場 (2)
タグ : / 解いたユーザー数 58
作問者 : hirakich1048576 / テスター : ixmel
問題文
数列 $ F_i $ を以下のように定義する.
$
\begin{cases}
F_0 = 0 \\
F_1 = 1 \\
F_{i+2} = F_{i+1} + F_i
\end{cases}
$
与えられる整数 $ N, M $ に対して, $ \large{ \sum_{i=1}^{n} F_{im} = \overbrace{F_m + F_{2m} + \cdots + F_{nm}}^{n} } $ を計算せよ.
答えは非常に大きな数になることがあるので,$ 1000000007 $で割った余りを答えよ.
入力
$ N \ M $
$ 1 \leqq N \leqq 10^{10} $
$ 2 \leqq M \leqq 30000 $
出力
$ \large{ \sum_{i=1}^{n} F_{im} = \overbrace{F_m + F_{2m} + \cdots + F_{nm}}^{n} } $ の値を$ 1000000007 $で割った余りを1行に出力せよ.
サンプル
サンプル1
入力
4 3
出力
188
$ F_1 $から$ F_{12} $の値は順に $ \normalsize{1, 1, \underline{\Large{2}}, 3, 5, \underline{\Large{8}}, 13, 21, \underline{\Large{34}}, 55, 89, \underline{\Large{144}}} $ なので,
$ 2 + 8 + 34 + 144 $の値$ 188 $が答えです.
サンプル2
入力
40964976 6561
出力
639430182
サンプル3
入力
8015993433 30000
出力
563904402
入力$ N $は32bit整数に収まらないことがあります.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。