GitHub 源文件 Markdown 中文

Grox's Sequence III

• Indicative time limit: 1.0 seconds.
• Judge time limit: twice the reference program’s largest per-case median on the target platform, rounded up to a multiple of 0.5 seconds.
• Memory limit: 512 MB.
• Reference environment and measurements

Story

That is why we proceed only from what we know, and why we constantly test what we believe to be true. We are rigorous with the truth, and ruthless.

— Spore, Book of Science Pt. 6

After you solve the second sequence problem, the Grox grow even fonder of you. They are still investigating how to solve the first sequence problem over a larger range, and discover yet another interesting sequence along the way.

This time, the Grox will give you several sets of parameters and ask you to calculate the corresponding results.

Formal Problem Statement

Given a nonnegative integer \(n\) and \(q\) queries, each query provides nonnegative integers \(a,b\) . Compute

\[ G(a,b)=\sum_{i=a}^{\min(n,n+a-b)}(i+b-a)!\prod_{k=a}^{i}k\pmod{921260340} \]

An empty sum is \(0\) when its upper bound is smaller than its lower bound. Define \(0!=1\) . Both product endpoints are included; in particular, when \(a=0\) , every product that occurs contains a factor of \(0\) .

Print the representative between \(0\) and \(921260339\) .

Input

The first line contains \(n,q\) . Each of the following \(q\) lines contains \(a,b\) .

Output

Print one answer per query on its own line.

Sample 1

Input

5 5
1 2
3 4
1 1
3 1
5 5

Output

3038
1512
15017
387
600

Sample 2

Input

0 3
0 0
1 0
0 1

Output

0
0
0

Sample 3

Input

3 4
1 0
0 1
4 1
2 2

Output

15
0
0
40

Sample Explanation

The last query of sample 1 has one term: \(G(5,5)=5!\cdot5=600\) . In sample 2, the first query has a zero product and the other two have empty sums.

Constraints and Guarantees

\(0\le n,a,b\le5000\) ; \(1\le q\le200000\) . The query indices \(a,b\) may exceed \(n\) .

Score	Additional conditions
100%	None