[2009国家集训队]密码系统

Lambda 受任于某情报站，负责获取敌方情报。一次破解密码系统时，他得到了一个 $N$ 位 $B$ 进制数 $\varphi$，满足

$$\varphi\equiv V\pmod M。$$

他发现，组成 $\varphi$ 的数字十分特殊。为了验证这种特殊性，他将所有满足模 $M$ 余 $V$ 的 $N$ 位 $B$ 进制数，按照其数位所构成的集合分类，并希望知道每一类中有多少个数。

输入格式

输入共一行，包含四个整数 $N$、$B$、$M$、$V$。

输出格式

输出共 $2^B-1$ 行。

每行包含一个非空集合 $S$ 和一个整数 $Ans[S]$，两者之间以单个空格分隔。

集合 $S$ 由其中所有元素按递减顺序排列后表示。例如，集合 $\{0,1,2\}$ 表示为 210。

$Ans[S]$ 表示数位集合恰好为 $S$，且满足题目条件的数的个数。所有集合按照其表示形式的字典序输出，每个集合只输出一次。

由于 $Ans[S]$ 可能很大，请输出其除以 $10007$ 所得的余数。

样例输入

3 3 4 1

样例输出

0 0
1 1
10 1
2 0
20 0
21 2
210 1

数据范围

• $N\le 10^9$；
• $B\le 10$；
• $M\le 110$。

来源与许可

本题为 2009 年国家集训队试题「密码系统」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 3 4 1

输出

0 0
1 1
10 1
2 0
20 0
21 2
210 1