Mr. M is given the task of solving problems of his colleagues. He has to do this for N days. Each day i (), he solves number of problems where . 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 such that
Here means + + .... + + (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 assuming he can solve x problems at any day where . Two ways are considered different if there exists a day i such that number of problems solved on that day differs. Print answer modulo .
Input contains only one line with four integers in order .
Output should contain required answer modulo
Author : Tanmay Patel
Following are the possible sequences:
Total : 10 + 10 + 1 + 1 + 1 + 1 = 24