题目描述
上个月21日(5月21日),是5·21事件一周年纪念日。为了庆祝这一天的到来,czh邀请了n个事件相关人来到Croom(一个地点)聚会。
这次聚会很奇怪。每一个进入Croom的人,都会被戴上一顶帽子,而这个人却不知道帽子的颜色。
等到被邀请的人物都到齐了,czh终于出现了。czh拿着话筒大声说道:
“我们首先来玩一个游戏,我当然不会参与。各位都看到了,到会的众位都戴着一顶帽子,有红的,也有黑的。每个人都不能看到自己的帽子的颜色,只能看到其他所有人帽子的颜色。等会儿会场的灯将全部熄灭,谁有完全的把握认为自己的帽子是红色的,谁就上台领取我为他准备的神秘礼物。如果没有人上台,那么灯将点亮,给各位一分钟的思考时间,然后又将重复上述过程,直到有人上台领奖为止。”
上述过程就这样重复着,终于在第m次熄灯之后有人上台领奖。
现在,你来猜猜一共有多少人上台领奖。
你可以假设:
1、每个人只能通过自己的推理得到帽子的颜色;
2、每个人都如czh一般聪明,在能推得自己帽子颜色的条件下一定能得到自己帽子的颜色;
3、每个人在熄灯时是否上台领奖,只决定与他在此次熄灯前的推理。
输入格式
共2行。
第1行:1个数n。
第2行:1个数m。
数据规模]
对于20%的数据,1<n <=10000。
对于100%的数据, n<=10^1000,1<=m<=n , 1<=p<=10^2
输出格式
第1行1个数p,表示有多少种可能的解。
若p>0,那么
第2~p+1行,每行1个数:若有k个人上台领奖,则输出k mod 100,000,000。
样例输入
样例输出