Given a sequence of n elements S with properly increasing integers. It means that the ith number must be less than the i+1th number. (Si < Si+1) Given a range number d, please count the number of the subsequences that the i+1th number is equal to or grater than the ith number. (S’i + d S’i+1, for every subsequence S’)
For example, S={1, 3, 5}, d=4. The answer is 7. The subsequences are {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, and {1,3,5}. If d=2, then the sequences will be {1}, {3}, {5}, {1,3}, {3,5}, and {1,3,5}.
Each test case starts with a line containing two integers n (1≤n≤106) and d (1≤d≤109) indicating the length of the sequence and the range between every two adjacent numbers. Following this is one line, containing n integers.
For each test case, out the number of the sequences according the rules. This number may be very large. Please output the number mod 100000077.