01环

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 01ring.in 输出文件 01ring.out

题目描述：
有足够多的0和1，组成一个长度为N的01环，要求不超过K个0是连续的，求满足条件的方案数。注意：循环同构会被认为是同一种方案。
输入文件（01ring.in）：
第一行有两个整数T，M，表示以下有T组数据。
每组数据占一行有两个整数N，K。
每组数据之间有一个空行隔开。
输出文件（01ring.out）：
输出T行，每行顺次对应一组测试数据。
每组数据你需要输出最后的方案数除以M的余数。
输入样例：
3 100000007

3 1

3 3

4 1

输出样例：
2
4
3
解释：
第一组数据的方案是：111，110。
第二组数据的方案是：111，110，100，000。
第三组数据的方案是：1111，1110，1010。
约束和限制：
对于20%的数据T<=20;
对于100%的数据T<=50;
对于20%的数据N,K<=20;
对于100%的数据N,K<=2000;
对于100%的数据 100,000,000<=M<=1,000,000,000 且M是素数。