Problem Background

You are likely very familiar with the seven-segment LED display, which is widely used in various digital devices such as calculators, watches, and traffic lights. Due to its simplicity and aesthetics, this design has been globally accepted. However, young Matej opposes this design and has created a "five-segment LED display," claiming it can achieve the same functionality more efficiently.

Problem Description

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

The substitution board consists of $m$ five-segment LED displays. The board will display a number, which is composed of $m$ digits representing the number of the substituted player. Matej decides to start demonstrating his substitution board operation. Initially, his board displays the number $x$. Matej will perform one of the following two operations:

• Turn on a segment of a closed LED.
• Turn off a segment of an open LED.

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

After performing $n$ operations, you will obtain a final state. For each final state that is a valid number, Matej wants to know how many different operation sequences satisfy the above constraints can reach these final states. Two operation sequences are considered different if and only if they operate on different five-segment LED displays at the $i$-th operation and result in different states at some point.

Input Format

The first line contains four integers $m, n, k, x$, as described in the problem statement.

Output Format

Output $10^m$ lines. The $i$-th line should contain an integer representing the number of all possible operation sequences for the final state displaying the number $i-1$, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

1 2 1 5

Sample Output #1

0
0
0
1
0
2
0
0
0
0

Sample Input #2

1 3 3 8

Sample Output #2

0
0
0
6
0
13
0
0
0
0

Sample Input #3

1 4 2 4

Sample Output #3

24
0
8
0
37
0
4
28
4
24

Notes/Hints

Sample 1 Explanation

Initially, the substitution board displays $5$. Since $k=1$, the board must display a valid number after each operation. Matej will perform $n=2$ operations, so he can end up displaying either $3$ or $5$. To display $3$, we can only change $5$ to $9$ and then to $3$. To display $5$, we can achieve this by either $5-9-5$ or $5-8-5$, hence there are two operation sequences.

Data Size and Constraints

This problem uses batched testing

• 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 data, $1 \leq k \leq n \leq 10^{15}$, $0 \leq x \leq 10^m$.

Notes

Translated from Croatian Olympiad in Informatics 2020 C Task Semafor.

见题面 Input 部分

见题面 Output 部分