U242229 乘积

现在我们有一个长度为 $n$ 序列 $a$，我们现在有 $k$ 个问题，对于每个问题，我们会给出两个数 $l$ 和 $r$，你需要求出从 $a_{l}$ 到 $a_{r}$ 的乘积模 $9999991$ 的结果。由于 $n$ 可能非常大，本题的序列 $a$ 由公式求得，即：$a_{1} = seed$，同时对于每个 $1 \leq i < n$，$a_{i+1} = max\{1,(a_{i} * (seed \% 997 + 1) * 7741 + 257099) \% 9999991\}$。

第一行两个数，表示 $n$，$m$ 和 $seed$。 接下来 $m$ 行，每行表示一组询问 $l$ 和 $r$。

$m$ 行，每行一个数，表示运算的结果。

### 样例 $1$ 解释 序列 $a = \{1,272581,359939,2837710,3722856\}$。 对于第一组询问，通过计算我们可以得知 $(359939 \times 2837710 \times 3722856) \% 999991 = 9976634$。 第二组询问计算过程同上。 --- ### 数据范围 | 测试点 | $n$ | $k$ | | :----------: | :----------: | :----------: | | $1$ | $\leq 50$ | $\leq 50$ | | $2$ | $\leq 1000$ | $\leq 1000$ | | $3$ | $\leq 1000$ | $\leq 5000$ | | $4$ | $\leq 1000$ | $\leq 5 \times 10^{5}$ | | $5$ | $\leq 10^{5}$ | $\leq 5 \times 10^{5}$ | | $6$ | $\leq 10^{6}$ | $\leq 5 \times 10^{5}$ | | $7$ | $\leq 2 \times 10^{7}$ | $= 1$ | | $8$ | $\leq 2 \times 10^{7}$ | $\leq 1000$ | | $9$ | $\leq 2 \times 10^{7}$ | $\leq 5 \times 10^{5}$ | | $10$ | $\leq 2 \times 10^{7}$ | $\leq 5 \times 10^{5}$ | 对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^{7},1 \leq k \leq 5 \times 10^{5},1 \leq seed \leq 9999991$。 #### 请注意：本体数据量非常大，虽然我们将时间限制开放到最大 $5$ s，但您在使用莫队的时候仍然可能需要使用优化，否则将只能获得 $50\%$ 的分数左右。另外，$std$ 代码对于测试点 $9,10$ 也需要消耗 $4.4$ s，你应当尽量删去不必要的代码并尽可能地做一些其他的优化例如快读。还有，线段树的速度可能会快很多，您可以尝试线段树，但请注意一些细节防止出现 MLE 的情况。另外，还有一种简单的做法只需要 $400$ ms，您可以思考一下