Mr. M and his Project

0

0 votes
Hard
Problem

Mr. M is given the task of solving problems of his colleagues. He has to do this for N days. Each day i (1<=i<=N), he solves Ai number of problems where 1<=Ai<=10. His boss has put a strange condition for his promotion. He will be promoted after N days if and only if there exists four days p,q,r,s such that

  • 1<=p<=q<r<s<=N
  • sum(p,q)=X
  • sum(q+1,r)=Y
  • sum(r+1,s)=Z


Here sum(x,y) means Ax + Ax+1 + .... + Ay1 + Ay (i.e. sum of problems solved from day x to day y).

Find the total number of ways Mr. M can receive promotion (number of distinct sequences A satisfying above conditions) for given values of N,X,Y,Z assuming he can solve x problems at any day where 1<=x<=10. Two ways are considered different if there exists a day i such that number of problems solved on that day differs. Print answer modulo 109+7.

Constraints:

  • 3<=N<=42
  • 1<=X,Y,Z<=6

Input Format:

Input contains only one line with four integers in order N,X,Y,Z.

Output Format:

Output should contain required answer modulo 109+7

Author : Tanmay Patel

Sample Input
4 1 5 1
Sample Output
24
Time Limit: 2.5
Memory Limit: 256
Source Limit:
Explanation

Following are the possible sequences:

  • {1, 5, 1, x} where 1 <= x <= 10 : 10 possible sequences
  • {x, 1, 5, 1} where 1 <= x <= 10 : 10 possible sequences
  • {1, 2, 3, 1}
  • {1, 3, 2, 1}
  • {1, 4, 1, 1}
  • {1, 1, 4, 1}

Total : 10 + 10 + 1 + 1 + 1 + 1 = 24

Editor Image

?