問題一覧 > 教育的問題

No.1892 Extended Fib Series

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : yassu0320yassu0320 / テスター : ShirotsumeShirotsume
0 ProblemId : 7979 / 自分の提出
問題文最終更新日: 2022-04-05 23:28:20

問題文

yassu君は、$N$ 段からなる階段を登ろうとしています。彼は一歩で高々 $L$ 段上ることができます。

$0$ 段目から出発し、$N$ 段目にたどり着くまでの移動方法が何通りあるかを求め、$10^9 + 7$ で割った余りを出力してください。

入力

$N\ L$

  • 入力は全て整数
  • $1 \leq N \leq 10^5$
  • $1 \leq L \leq 10^5$

出力

移動方法の数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
4 3
出力
7

条件を満たす移動方法は以下の7通りです:

  • $0$ 段目 $\rightarrow 1$ 段目 $\rightarrow 2$ 段目 $\rightarrow 3$ 段目 $\rightarrow 4$ 段目
  • $0$ 段目 $\rightarrow 1$ 段目 $\rightarrow 2$ 段目 $\rightarrow 4$ 段目
  • $0$ 段目 $\rightarrow 1$ 段目 $\rightarrow 3$ 段目 $\rightarrow 4$ 段目
  • $0$ 段目 $\rightarrow 1$ 段目 $\rightarrow 4$ 段目
  • $0$ 段目 $\rightarrow 2$ 段目 $\rightarrow 3$ 段目 $\rightarrow 4$ 段目
  • $0$ 段目 $\rightarrow 2$ 段目 $\rightarrow 4$ 段目
  • $0$ 段目 $\rightarrow 3$ 段目 $\rightarrow 4$ 段目

サンプル2
入力
1 1
出力
1
サンプル3
入力
1000 50
出力
438993203

$10^9+7$ で割った余りを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。