Bob has a huge fuzzy grid so he wants you to make it as clear as possible.
He will give you four integers N,M, K, X and an empty grid of N rows and M columns. You need to fill the grid with integers from 1 to K such that the absolute difference between maximum elements of any two consecutive rows is at most X.

Find the total number of ways to fill the grid. Since the answer may be very large return it modulo 10^9+7.

function to complete:
int helper(int N, int M, int K, int X){}

Constraints
N: 1 to 10^4
M: 1 to 10^9
K: 1 to 10^3
X: 0 to K-1

Sample input
3
3
1
0

Output
1

A farmer planted N trees such that the initial height of the ith tree is given as A[i].

He noticed that the growth of trees is slow so he started giving them fertilizers.

He knows that the j-th tree will grow by B[j] in the next day if he gives it one piece of fertilizer on any day, However he may choose to give a tree any amount of fertilizer he wants.

This means that if the j-th tree has a growth rate of (B[j]= 1) and the farmer puts one piece of lestilizer in it and its height was previously (A[j] = 2) then the next day it will be (A[j] = 3) However, it a tree with initial height(A[j]) of 5 and growth B[j] = 3 then if the farmer giver it two units of fertilizer it's height will became 11 the next day.

It is given that the farmer does not want some trees to exceed a certain height and may choose to shorten them.

The farmer has a smart tractor, which distributes the fertilizers to successive chains of trees with a specified amount of fertilizer, ensuring that the fertilizer reaches all the trees

There are two type of operations of the type (T, L, R, K) that the farmer will perform for the next Mdays:

• The first operation is performed when (T[i] = 1) In this operation the tractor will add k[i] pieces of fertilizer to the trees from from L[i] to R[i]

• The second operation is performed when (T[i] = 2) In this operation the farmer wants to inquire about the j-th tree, where (j = R[i] - L[i] + 1) If its height (A[j]) exceeds the amount K[i] he will cut from it the amount of [(Aj - K)] The integer part of the value be taken K[i] / 2 will be taken.
Find the sum of all heights of the trees after M days. Since the answer can be very large return it modulo 10^9+7.

Function format:
int Solve(int N, int M, vector<int> A, vector<int> B, vector<int> T, vector<int> L, vector<int> R, vector<int> K){}