No.8046 yukicoder's Past Problem
タグ : / 解いたユーザー数 39
作問者 :
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
0Only 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もしくは右上の雲マークをクリックしてアカウントを作成してください。