# Grox的序列三

- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

> 这就是为什么我们只进行我们所知道的，以及为什么我们持续测试我们相信是事实的。我们坚信真理。
>
> ——科学之书6（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

解决了第二道序列问题后，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

### 输入

```text
5 5
1 2
3 4
1 1
3 1
5 5
```

### 输出

```text
3038
1512
15017
387
600
```

## 样例 2

### 输入

```text
0 3
0 0
1 0
0 1
```

### 输出

```text
0
0
0
```

## 样例 3

### 输入

```text
3 4
1 0
0 1
4 1
2 2
```

### 输出

```text
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% | 无额外条件 |