A bot starts at tile 0 on an infinite strip of tiles numbered 0, 1, 2, .... In one hop it moves forward by one of k allowed step lengths (each may be reused any number of times, in any order). Count the number of distinct ORDERED hop sequences that land the bot exactly on tile n (two sequences are distinct if they differ in the step length used at some hop, or in the number of hops). Since this count can be large, print it modulo 1000000007.
Line 1: two integers n k.
Line 2: k distinct space-separated positive integers, the allowed step lengths.
A single integer: the number of ordered hop sequences landing exactly on tile n, modulo 1000000007. (If n = 0, the empty sequence counts, so the answer is 1.)
Example 1
Input
4 2 1 2
Expected
5
Explanation
Using steps of 1 and 2, the sequences reaching 4 are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 — 5 total.
Example 2
Input
0 2 3 5
Expected
1
Explanation
The bot is already at tile 0, so the only valid sequence is the empty one: answer 1.
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 →