题目名称	2666. [HZOI 2015] Keller与驴蛋蛋与海蜇
输入输出	`seaHibernate.in/out`
难度等级	★★★★
时间限制	4000 ms (4 s)
内存限制	64 MiB
测试数据	20
题目来源	YGOI_真神名曰驴蛋蛋于2017-04-18加入
开放分组	全部用户
提交状态
分类标签	HZOI FFT
	分享题解

通过：5，提交：20，通过率：25%
The dark	100	33.593 s	8.81 MiB	C++
FoolMike	100	43.110 s	8.81 MiB	C++
YGOI_真神名曰驴蛋蛋	100	44.871 s	20.56 MiB	C++
shy	100	65.309 s	40.75 MiB	C++
策	100	67.062 s	25.98 MiB	C++
Go灬Fire	50	3.791 s	99.55 MiB	C++
FoolMike	50	43.153 s	8.81 MiB	C++
miaom	50	60.150 s	1.93 MiB	C++
miaom	50	136.104 s	1.24 MiB	C++
miaom	50	140.608 s	1.31 MiB	C++

关于 Keller与驴蛋蛋与海蜇的近10条评论(全部评论)
回复 @FoolMike : 核电MIKE刷上rank1 HZOI_蒟蒻一只 2017-07-02 19:27 17楼
忘记了(x+block)!/x!是个block次多项式，有block+1项，不是block项…… FoolMike 2017-07-02 17:19 16楼
数据有误请联系驴蛋蛋 YGOI_真神名曰驴蛋蛋 2017-04-25 06:00 15楼
居然有人过了。。。 Go灬Fire 2017-04-24 18:52 14楼
然而图是乌贼娘。。。（好像不是重点） Hyoi_0Koto 2017-04-22 16:34 13楼
兹瓷鱼蛋蛋 Sky_miner 2017-04-19 19:31 12楼
回复 @假神名曰Keller : 为啥没有鱼蛋蛋了呢哒哒哒哒哒！ 2017-04-19 19:26 11楼
回复 @Go灬Fire : 贵校这波头像是要搞事情么233333 沉迷学习的假的Keller 2017-04-19 10:31 10楼
图不是乌贼吗？为什么海里有煮熟的虾（跑 6666 2017-04-19 10:15 9楼
orz驴蛋蛋！ heoi2017走啊！我主场！come on！ HZOI_蒟蒻一只 2017-04-19 09:27 8楼

2666. [HZOI 2015] Keller与驴蛋蛋与海蜇

★★★★ 输入文件：seaHibernate.in 输出文件：seaHibernate.out 简单对比
时间限制：4 s 内存限制：64 MiB

【题目描述】

众所周知，海蜇是一个有$C$个点$C$条边的无向连通图

现在$Keller$想要吃海蜇，驴蛋蛋自告奋勇的去抓。

抓海蜇要先到达大海，$Keller$为驴蛋蛋提供了一种交通工具，使驴蛋蛋可以在$K$维空间中任意爬行(?)

一开始驴蛋蛋在原点$(0,0,0,0…0)$,每一秒钟驴蛋蛋要在某一维上向远离原点的方向移动一步。比如在$2$维空间中，驴蛋蛋只能以$(+1,0)$,$(0,+1)$的步长移动,而$(0,-1)$,$(-1,0)$和$(0,0)$的步长都是不被允许的。也就是说驴蛋蛋每秒必须使TA的某一维坐标增加1。

现在驴蛋蛋想知道他在多少秒后到达点$(N,N,N,…N)$。

然而$Keller$却想知道驴蛋蛋到达点$(N,N,N…N)$的方案数是多少,两种方案不同当且仅当某一秒钟驴蛋蛋的移动决策不同。

$Keller$告诉驴蛋蛋,若驴蛋蛋某时刻的坐标是$(a1,a2,a3…ak)$,那么必须有$a1\ge a2\ge a3\ge…\ge ak$

驴蛋蛋傻了，请你帮助驴蛋蛋做出来。

答案对P取模。$P=a*2^k+1$保证$a,P$均为质数且$k\ge 16$

$P≤2*10^9,k≥16,N\le3*10^4,2\le K\le 3*10^4$

【输入格式】

第一行有一个整数$P$和一个整数$T$,$T$表示有$T$组测试数据$(T\le1000)$

然后接下来有$T$行,每行两个正整数$K,N$

【输出格式】

每行一个整数表示$Keller$要求的答案

【样例输入】

469762049 3

2 116

4 69

3 15

【样例输出】

291788030

323538158

250998049

【提示】

前$50\%$的数据满足$2\le K\le 5$

【来源】

驴蛋蛋的脑冻