You climb a staircase of n stairs. You are given a set of m distinct allowed stride lengths. Each move you take goes up by one of the allowed stride lengths. Count the number of ordered sequences of moves whose lengths add up to exactly n (two sequences that use the same multiset of strides in a different order are counted separately).
Report the count modulo 1000000007. Climbing 0 stairs has exactly one sequence: the empty one.
Line 1: two integers n and m.
Line 2: m space-separated distinct positive integers, the allowed stride lengths.
A single integer: the number of ordered stride sequences summing to n, modulo 1000000007.
Example 1
Input
4 2 1 2
Expected
5
Explanation
Ordered sequences of 1s and 2s summing to 4: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 — that is 5.
Example 2
Input
7 1 2
Expected
0
Explanation
With only stride 2, no sequence sums to the odd total 7, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →