#P18154. Array Spread

Array Spread

Array Spread

Vasya 想构造一个长度为 nn、元素为非负实数的数组 aa。

他还有 mm 个区间 [l1,r1],[l2,r2],…,[lm,rm][l_1,r_1],[l_2,r_2],\dots,[l_m,r_m](1≤li≤ri≤n1\le l_i\le r_i\le n),它们定义了 aa 的 mm 个子数组。

定义数组 aa 的散布度如下:

  • 计算子数组和 si=∑j=liriajs_i=\sum_{j=l_i}^{r_i}a_j;
  • 散布度为
max⁡j=1msjmin⁡j=1msj.\frac{\max_{j=1}^{m}s_j}{\min_{j=1}^{m}s_j}.

若 min⁡jsj=0\min_j s_j=0,则散布度为 +∞+\infty。

求所有可能的数组 aa 中散布度的最小值。保证最小值存在。答案对 998244353998244353 取模。

可以证明答案可以写成互素的 pq\frac{p}{q},且 q≢0(mod998244353)q\not\equiv0\pmod{998244353};输出 p⋅q−1 mod 998244353p\cdot q^{-1}\bmod 998244353。

输入格式

第一行一个整数 tt(1≤t≤20001\le t\le 2000)。

每组测试:

  • 第一行两个整数 n,mn,m(1≤n≤1091\le n\le 10^9,1≤m≤20001\le m\le 2000);
  • 接下来 mm 行,每行两个整数 li,ril_i,r_i(1≤li≤ri≤n1\le l_i\le r_i\le n)。

保证所有测试的 mm 之和不超过 20002000。

输出格式

每组测试输出一个整数,表示答案对 998244353998244353 取模。

样例

输入:

3
3 3
1 3
2 3
1 2
12 6
2 3
5 7
1 9
4 8
1 2
7 11
4 5
3 4
2 3
1 2
4 4
1 1

输出:

1
2
499122178

第一组可以取a=[0,3,0],三个区间和都是3。第二组可以取a=[0,1,0,0,1,0,0,0,0,0,2,0],区间和依次为[1,1,2,1,1,2]。第三组可以取a=[2,1,1,2],区间和为[3,2,3,2,2]。

第三组的最小散布度为 3/23/2,499122178≡3⋅2−1(mod998244353)499122178\equiv 3\cdot2^{-1}\pmod{998244353}。