At Prof. TOI's prototype electric vehicle factory, the machine that manufactures electric vehicle parts has $$$2^K-1$$$ pieces, where $$$K$$$ is the number of layers in which the pieces are connected. Layer $$$K$$$ contains $$$2^{K-1}$$$ pieces. The first layer contains only one piece, numbered 1. Pieces in the next layers are numbered continually from the previous layer according to the connection scheme. That is, piece numbered $$$m$$$ is connected to pieces numbered $$$2m$$$ and $$$2m+1$$$ in the next layer.
Operating this machine requires cutting $$$N$$$ contiguous power cells into $$$2^{K-1}$$$ chunks to feed into all of the pieces in layer $$$K$$$. Each piece of the machine has a power value, which can be calculated as follows:
- If the piece is in layer $$$K$$$, the power value is equal to the total value of energy cells fed into it
- Each piece in layer $$$i$$$, that is not layer $$$K$$$, has the power value equal to the sum of the power values of the connected pieces in layer $$$i+1$$$ (in which there are 2 pieces). In order for the machine to operate properly, both pieces in layer $$$i+1$$$ that connects to the same piece in layer $$$i$$$ must have their power values differ by at most $$$D$$$.
Figure 1 displays 13 power cells In the case $$$D=5$$$, there are 4 possible methods of dividing the power cells to feed the machine, as shown in Figures 2-5.
Figure 2 displays method 1 of dividing power cells 
Figure 3 displays method 2 of dividing power cells 
Figure 4 displays method 3 of dividing power cells 
Figure 5 displays method 4 of dividing power cells Your Task
Write an efficient program to determine the total number of possible methods of dividing power cells according to the restrictions, giving the answer as the remainder when dividing the number by 1,000,000,007
There are 2 lines of input:
| Line 1 | 3 integers separated by a space. The first integer is $$$N$$$, denoting the number of power cells. The second integer is $$$K$$$, denoting the number of connected layers in the machine. The third integer is $$$D$$$, denoting the largest difference of the power values for two pieces in layer $$$i+1$$$ that connects to the same piece in layer $$$i$$$ ($$$1\leq i\leq K−1$$$). Let
|
| Line 2 | contains $$$N$$$ values of $$$A_j$$$, denoting the power value of power cell $$$j$$$, where $$$1\leq A_j\leq 1{,}000$$$, $$$1\leq j\leq N$$$. |
There is 1 line of output:
| Line 1 | 1 integer denoting the total number of possible methods of dividing power cells. For every input, there is always at least 1 method of dividing power cells. Output the answer as the remainder when dividing the number by 1,000,000,007 |
Notices regarding the test sets are as follows:
| Test Group | Maximum attainable score in this group | Condition(s) |
| 1 | 2 | $$$K=2$$$ and $$$N\leq 50$$$ |
| 2 | 3 | $$$K=3$$$ and $$$N\leq 50$$$ |
| 3 | 6 | $$$K=3$$$ |
| 4 | 17 | $$$2^{K-1}\leq N\leq 2^{K-1}+3$$$; that is, there are 3 more power cells than there are pieces at the bottom layer. |
| 5 | 28 | $$$N\leq 50$$$ |
| 6 | 44 | No additional constraints |
13 3 5 8 7 4 2 8 5 3 5 2 5 3 7 7
4
14 2 6 1 1 2 1 2 3 1 2 1 2 3 4 2 1
5
Recommended programming tips
If the contestant uses cin/cout, it is recommended to add 2 lines as the following:
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
