Description

Matej's first step is to apply this design to the football industry. He is currently giving a presentation at the Croatian Football Federation, planning to use his design on the substitution board.

The substitution board consists of $m$ five-segment LED displays. The board will show a number made of $m$ digits, representing the jersey number of the player being substituted off. Matej decides to start demonstrating how his board works. At the beginning, his board shows the number $x$. Matej will perform one of the following two operations:

• Turn on one LED segment that is currently off.
• Turn off one LED segment that is currently on.

Matej will perform a total of $n$ operations. He must ensure that after every $k$ operations, the board shows a valid number (i.e., each five-segment LED display shows a digit from $0$ to $9$).

After performing $n$ operations, you will get a final state. For each final state that is a valid number, Matej wants to know how many different operation sequences satisfying the above restriction can reach that final state. We say two operation sequences are different if and only if, at the $i$-th operation, they operate on different five-segment LED displays, and after some operation the two sequences result in different states.

Input Format

The first line contains four integers $m,n,k,x$, as described above.

Output Format

Output $10^m$ lines. On the $i$-th line, output an integer denoting the number of operation sequences such that the final displayed number is $i-1$. Output the answer modulo $10^9+7$.

1 2 1 5

0
0
0
1
0
2
0
0
0
0

1 3 3 8

0
0
0
6
0
13
0
0
0
0

1 4 2 4

24
0
8
0
37
0
4
28
4
24

Hint

Explanation for Sample 1

At the beginning, the substitution board shows $5$. Since $k=1$, after each operation the board must show a valid number. Matej will perform $n=2$ operations, so in the end he can display either $3$ or $5$. To display $3$, we can only first change $5$ into $9$, and then change $9$ into $3$. To display $5$, we can do it either by $5-9-5$ or by $5-8-5$, so there are two operation sequences.

Constraints

This problem uses bundled testdata.

• Subtask 1 (6 pts): $m=1$, $1 \leq n \leq 12$.
• Subtask 2 (15 pts): $m=1$, $1 \leq n \leq 10^{15}$.
• Subtask 3 (12 pts): $m=2$, $1 \leq n \leq 1500$, $k=n$.
• Subtask 4 (12 pts): $m=2$, $1 \leq n \leq 10^{15}$, $1\leq k \leq 15$.
• Subtask 5 (15 pts): $m=2$, $1 \leq n \leq 10^{15}$, $1\leq k \leq 1500$.
• Subtask 6 (40 pts): $m=2$, $1 \leq n \leq 10^{15}$.

For $100\%$ of the testdata, $1 \leq k \leq n \leq 10^{15}$, $0 \leq x \leq 10^m$.

Notes

Translated from Croatian Olympiad in Informatics 2020 C Semafor。

Translated by ChatGPT 5