P8429 [COI 2020] Semafor

You may be very familiar with the seven-segment LED display, which is widely used in many digital devices such as calculators, watches, traffic lights, and so on. Because it is simple and good-looking, this design has been accepted worldwide. However, the young Matej objects to this design and came up with a "five-segment LED display", claiming that it can achieve the same functionality as the seven-segment LED display more efficiently. 

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.

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

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$.

#### 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](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。 Translated by ChatGPT 5