你可能很熟悉所谓的 7 段数码管，它被广泛用于在各种电子设备（如手表或计算器）上显示数字。由于其简单、直观和美观，这种设计已被全球接受。然而，年轻的 Matej 对 7 段数码管的设计提出了异议，并声称只需使用 5 个段就可以更高效地实现相同的功能。

5段数码管设计——各段用字母 a 到 e 标记。

Matej 决定在克罗地亚经济最繁荣的领域——足球中迈出他的创业第一步。他的革命性设计将在克罗地亚足球甲级联赛（1. HNL）的比赛中用作换人板。他目前正在向克罗地亚足球协会的董事会进行演示。

换人板由 $M$ 个 5 段数码管组成，从左到右分别代表即将下场的球员的球衣号码的各位数字。在 Matej 演示开始时，换人板显示的数字为 $X$，Matej 每秒会进行以下操作之一：

• 点亮一个当前熄灭的段。
• 熄灭一个当前点亮的段。

Matej 总共将进行 $N$ 次操作，并且他会确保每进行 $K$ 次操作后（即在第 $K, 2K, 3K, \dots$ 次操作后），换人板上显示的都是一个合法的数字。如果数字的每一位都在对应的数码管上正确显示（即点亮的段组成一个合法的数字），则该数字是合法的。此外，如果显示的数字不足 $M$ 位，则需要包含适当数量的前导零以构成合法的显示。

对于每个最终状态（介于 $0$ 和 $10^M - 1$ 之间的整数），Matej 想知道在演示过程中有多少种不同的操作方式可以使最终达到该状态。当然，他需要遵守前面提到的所有限制。如果我们将两组操作序列想象为同时在两块不同的换人板上执行，且在某一时刻这两块板呈现出不同的状态，则认为这两组操作序列是不同的。

由于不同方式的数量可能非常大，请将其对 $10^9 + 7$ 取模后输出。

输入格式

第一行包含任务描述中的整数 $M, N, K$ ($1 \le K \le N$) 和 $X$ ($0 \le X < 10^M$)。

输出格式

输出共 $10^M$ 行。在第 $i$ 行中，你应该输出在 Matej 演示结束时，换人板显示数字 $i - 1$ 的不同操作方式的数量。这些数字应该对 $10^9 + 7$ 取模后输出。

子任务

样例

输入样例 1

1 2 1 5

输出样例 1

0
0
0
1
0
2
0
0
0
0

输入样例 2

1 3 3 8

输出样例 2

0
0
0
6
0
13
0
0
0
0

输入样例 3

1 4 2 4

输出样例 3

24
0
8
0
37
0
4
28
4
24

说明

样例 1 说明：在演示开始时，（单数字）换人板显示的数字为 $5$。由于 $K = 1$，在每次操作后，换人板都必须显示一个合法的数字。Matej 总共将进行 $N = 2$ 次操作。因此，在演示结束时，换人板可以显示数字 $3$ 或数字 $5$。得到数字 $3$ 有 $1$ 种方式（$5 \to 9 \to 3$），得到数字 $5$ 有 $2$ 种方式（$5 \to 9 \to 5$ 和 $5 \to 8 \to 5$）。