little pony is enjoying his summer vaccation but in the meantime he also wants to be productive and enhance his skills.
there are N days left in the vaccation and there are M types of activities number from 0 to M-1 which he can do during these n days. there is a boredom limit associated with each of these m activites that is he does not want to perfrom i th activiity for more than A[i] consecutive days.
can you find the total number of ways to spend these N days doing exactly one activity on each day?
Two ways are different if there exist a day such that activity done on this day and second way is different.
since the answer is very large, return it modulo 10^9+7.
input format-
the first argument is the integer N.
the second argument is the array A of size M.
output- your function should return an integer corresponding to the answer.
example-
input-1
N=3
M=2
A=[1,2]
input-2
N=5
M=3
A=[4,4,4]
output 1:
4
output 2:
40
Example explanation
since we have 2 choice(let’s say 0 and 1) for each day there are total 8 ways to perfrom this activities.
000-invalid,more than 1 zero’s are together
001-invalid,more than 1 zeros’s are together
010-valid
011-valid
100-invalid,more than 1 zero’s are together
101-valid
110-valid
111- invalid ,more than 2 one’s are together
thus, our answer is .
