#1028. 2032. [2009国家集训队]密码系统

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

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

题目描述

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

输入格式

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

输出格式

共2B-1行,每行包含一个集合S和整数Ans[S],以单个空格隔开。集合S用其所有元素的递减序列表示,如{2, 0, 1}表示为"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  

【样例说明】  

在所有三位三进制数(1003~2223)中,模4为1的数为1003, 1113, 1223, 2103, 2213。数位集合为{1}的有1个(1113)  

,数位集合为{1, 0}的有1个(1003),数位集合为{2, 1}的有2个(1223, 2213),数位集合为{2, 1, 0}的有1个(2103)。  

数据范围与提示

N< = 10 ^ 9 B< = 10 M< = 40