P8429 [COI 2020] Semafor

你可能非常熟悉七段 LED 显示器，它广泛地应用于各种数字设备内，比如计算器，手表，红绿灯等等。由于它的简单与美观，该设计已被全球接受，不过年轻的 Matej 反对这个设计，并设计出了"五段 LED 显示器"，声称可以更有效地获得与七段 LED 显示器相同的功能。 

Matej 的第一步就是将这项设计应用到足球业界中，他目前正在克罗地亚足球协会中做演讲，决定将他的设计用在换人板上。 换人板由 $m$ 个五段 LED 显示器组成，换人板将显示一个数，这个数由换人板上的 $m$ 个数字组成，代表被换下的球员的号码。Matej 决定开始演示他的换人板操作。刚开始他的换人板上显示了数字 $x$。Matej 将做出下面两种操作的一种： * 将一段关闭的 LED 灯打开。 * 将一段打开的 LED 灯关闭。 Matej 总共会执行 $n$ 次操作，他需要保证每 $k$ 次操作他的换人板显示的是一个数（每个五段 LED 显示器上都显示了一个 $0$ ~ $ 9$ 内的数字）。 执行完 $n$ 次操作后你会得到一个最终状态，对于每个最终状态是一个数的情况，Matej 想知道分别有多少种满足上述限制的不同的操作序列能达到这些最终状态。我们说两个操作序列不同，当且仅当这两个操作序列中第 $i$ 次操作时操作了不同的五段 LED 显示器并且在某此操作后两种操作序列产生的状态不同。

第一行四个整数 $m,n,k,x$，意义见题目描述。

共 $10^m$ 行。第 $i$ 行输出一个整数表示最终状态显示的数为 $i-1$ 时所有的操作序列的个数。答案对 $10^9+7$ 取模。

#### 样例 1 解释 刚开始的时候换人板上显示 $5$。因为 $k=1$。所以每次操作后换人板上都必须显示的是一个数。Matej 将会进行 $n=2$ 次操作，因此最终他可以显示出 $3$ 或 $5$ 两个数。为了显示 $3$，我们只能先将 $5$变成 $9$ 然后再将 $9$ 变成 $3$。为了显示 $5$，我们即可以通过 $5-9-5$ 的方法实现也可以通过 $5-8-5$ 的方法实现，因此有两种操作序列。 #### 数据规模与约定 **本题采用捆绑测试。** * 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}$。 对于 $100\%$ 的数据，$1 \leq k \leq n \leq 10^{15} $，$0 \leq x \leq 10^m$。 ### 说明 翻译自 [Croatian Olympiad in Informatics 2020 C Semafor](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。