Grox的序列三¶
- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
- 参考评测环境与测量
背景故事¶
这就是为什么我们只进行我们所知道的，以及为什么我们持续测试我们相信是事实的。我们坚信真理。
——科学之书6（《Spore》，英文资料）
解决了第二道序列问题后，Grox 对你的好感继续上升。他们仍在研究第一道序列问题扩大范围后的解法，又从中发现了一个有意思的序列。
这一次，Grox 会多次给出参数，请你计算对应的结果。
形式化问题描述¶
给定非负整数 \(n\) 和 \(q\) 次询问。每次给出非负整数 \(a,b\) ，计算
\[
G(a,b)=\sum_{i=a}^{\min(n,n+a-b)}(i+b-a)!\prod_{k=a}^{i}k\pmod{921260340}
\]
若求和上界小于下界，空和等于 \(0\) .\(0!=1\) .乘积的两个端点均包含；特别地，\(a=0\) 时每个存在的乘积均含因子 \(0\) .
输出答案在 \(0\) 到 \(921260339\) 之间的代表元。
输入格式¶
第一行两个整数 \(n,q\) .接下来 \(q\) 行，每行两个整数 \(a,b\) .
输出格式¶
输出 \(q\) 行，每行一个询问的答案。
样例 1¶
输入¶
5 5
1 2
3 4
1 1
3 1
5 5
输出¶
3038
1512
15017
387
600
样例 2¶
输入¶
0 3
0 0
1 0
0 1
输出¶
0
0
0
样例 3¶
输入¶
3 4
1 0
0 1
4 1
2 2
输出¶
15
0
0
40
样例解释¶
样例一的最后一问只有一项，\(G(5,5)=5!\cdot5=600\) .样例二中，第一问的乘积为零，其余两问为空和。
数据范围与保证¶
\(0\le n,a,b\le5000\) ；\(1\le q\le200000\) .不保证 \(a,b\le n\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |