Rain_w and Calculate

题号：NC231693
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Rain_w doesn't like calculate. So she wants you to help her with some questions. Firstly, Rain_w will give you an integer $k$ and an integer $q$ . Then she will ask you $q$ questions. For the i-th question, she will give you two integers $l_i$ and $r_i$ , then you should help her to calculate $\sum_{s=l_i}^{r_i}s^k$ . Because this number may be too large, she wants you to output this answer modulo 998244353. Please help her!

输入描述:

The first line contains two integers  separated by a space.
Next  lines, the i-th line contains two integers  separated by a space, which describes the i-th question.

输出描述:

Your output should contain  lines. For the i-th line, you should output an integer in range , which is the answer of .

示例1

输入

复制

2 5
1 9
2 6
8 17
95 95
9999999 10000000

输出

复制