Croatian Olympiad in Informatics
October \(3^{rd}\) 2020
You are most likely familiar with a \(so-ca\)lled \(7-se\)gment display which is widely used to depict digits on
various digital devices, such as watches or calculators. Due to its simplicity, intuitiveness and aestheticism,
this design has been accepted across the globe. Still, young Matej argues against the \(7-se\)gment design
and claims that the same functionality can be obtained more efficiently, using only 5 segments.
\(5-se\)gment display design – segments are labeled with letters from a to e.
Matej decided to make his first entrepreneurial steps in the most prosperous branch of Croatian economy,
football. His revolutionary design will be used on a substitution board during the games of 1. HNL.^{1} He
is currently making a presentation for the board of directors at the Croatian Football Association.
The substitution board consists of \(M\) \(5-se\)gment displays which, from left to right, represent the digits
of a jersey number worn by the player that is about to leave the pitch. At the beginning of Matej’s
presentation, the substitution board represents the number \(X\), and Matej will make one of the following
moves each second:
• Turn on one segment that is currently turned off.
• Turn offone segment that is currently turned on.
In total, Matej will make \(N\) moves and he will make sure that after each \(K-th\) move, the board shows a
valid number. The number is valid if each of its digits is correctly shown on the corresponding display
(i.e. segments that are turned on show a valid digit). Also, numbers having less than \(M\) digits are validly
shown if they contain the appropriate number of leading zeros.
For each final state (integer between 0 and \(10^{M} - 1\)), Matej is interested in how many different ways could
he make his moves during the presentation such that this final state is reached at the end. Of course, he
needs to adhere to all limitations presented in the previous chapters. We consider two sequences of moves
different if, imagining they are executed on two different boards at the same time, there is a moment at
which the two boards represent a different state.
Since the number of different ways can be quite large, you are asked to compute it modulo \(10^{9} + 7\).
^{1}The elite tier of Croatian professional football.
5 od 8
Croatian Olympiad in Informatics
October \(3^{rd}\) 2020

Subtask
Score
Constraints
1
6
\(M = 1\), \(1 \le N \le 12\)
2
15
\(M = 1\), \(1 \le N \le 10^{15}\)
3
12
\(M = 2\), \(1 \le N \le 1\,500\), \(K = N\)
4
12
\(M = 2\), \(1 \le N \le 10^{15}\), \(1 \le K \le 15\)
5
15
\(M = 2\), \(1 \le N \le 10^{15}\), \(1 \le K \le 1\,500\)
6
40
\(M = 2\), \(1 \le N \le 10^{15}\)

The first line contains integers \(M\), \(N\), \(K\) (\(1 \le K \le N\)) and \(X\) (\(0 \le X < 10^{M}\)) from the task description.

In the \(i-th\) line you should output the number of different ways for the substitution board to show the
number \(i - 1\) at the end of Matej’s presentations. The numbers should be printed modulo \(10^{9} + 7\).

생성자가 기록되지 않았습니다.

출처 COCI 2019/2020 Olympiad