問題一覧 > 教育的問題

No.8046 yukicoder's Past Problem

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : mai
お気に入りにしたユーザー ProblemId : 2744 / 自分の提出
問題文最終更新日: 2021-03-06 18:16:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder April Fool Contest 2019 (順位表) の他の問題:

note

This problem was created for yukicoder April fool contest 2019.

Problem Statement

There is a staircase with $K$ steps.
Takeya might climb 1, 2, or 3 steps at a time, and Y might climb 1 or 2 steps at a time, but Maiha can climb the stairs by any one of $x_1, x_2,\ldots,x_N$ steps with a single stride.

In how many ways can Maiha climb exactly $K$ steps of the staircase?
Since the answer can be very large, print the remainder when it is divided by $1000000007$.

Input

$K$
$N$
$x_1\ x_2\ \ldots\ x_N$

$1 \le K \le 10^5$
$1 \le N \le 10^5$
$1 \le x_i \le 10^5$
$x_i < x_{i+1}$
All values are integers, written in decimal notation.

Output

Print a newline at the end.

Sample

Sample 1
Input
4
2
1 3
Output
3

There are the following 3 ways. "3 steps, 3 steps" exceeds 4 steps, so it is not counted.

  • 1 step, 1 step, 1 step, 1 step
  • 1 step, 3 steps
  • 3 steps, 1 step
Sample 2
Input
9
2
1 2
Output
55

This input has the same meaning as No.786 Kyoto University's Past Exam Problem, Sample 2.

Sample 3
Input
11
4
2 4 6 8
Output
0
Only an even number of steps can be climbed at a time, so there is no combination that climbs exactly 11 steps.

Sample 4
Input
100000
4
1 2 4 8
Output
30131883

Print the remainder when divided by $1000000007$.

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