题目描述

Lambda 受任于某情报站，他的工作是获取敌人情报。一次他在破解密码系统时，得到了一个 $N$ 位 $B$ 进制数 $\phi$ ，满足 $\phi \equiv V(\mod M)$。他发现组成 $\phi$ 的数字很奇特。为了验证 $\phi$ 的特殊性，他将所有模 $M$ 为 $V$ 的 $N$ 位 $B$ 进制数，按照各数位构成的集合分类，并想知道每一类数各有多少个。

输入格式

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

输出格式

共 $2B-1$ 行，每行包含一个集合 $S$ 和整数 $Ans_S$，以单个空格隔开。集合 $S$ 用其所有元素的递减序列表示，如${2,0,1}$ 表示为 $210$。$Ans_S$表示数位集合为 $S$ 的满足以上性质的数的数目。集合按照字典序输出，每个集合只输出一次。由于 $Ans_S$ 可能很大，只需输出它除以 $10007$ 的余数即可。

样例输入

3341

样例输出

00
11
101
20
200
212
2101

样例说明

在所有三位三进制数（ $(100)_3 \sim (222)_3$ ）中，模 $4$ 为 $1$ 的数为 $(100)_3,(111)_3,(122)_3,(210)_3,(221)_3$。数位集合为 ${1}$ 的有 $1$ 个（$(111)_3$），数位集合为 ${1,0}$ 的有 $1$ 个（$(100)_3$），数位集合为 ${2,1}$ 的有 $4$ 个（$(122)_3,(221)_3$），数位集合为 ${2,1,0}$ 的有 $1$ 个（$(210)_3$）。

数据规模与约定

对于 $100\%$ 的数据，$N\leq10^9$，$B\leq10$，$M\leq40$。

题目来源

版权所有者：赖陆航