Array Spread
Vasya 想构造一个长度为 n、元素为非负实数的数组 a。
他还有 m 个区间 [l1,r1],[l2,r2],…,[lm,rm](1≤li≤ri≤n),它们定义了 a 的 m 个子数组。
定义数组 a 的散布度如下:
- 计算子数组和 si=∑j=liriaj;
- 散布度为
minj=1msjmaxj=1msj.
若 minjsj=0,则散布度为 +∞。
求所有可能的数组 a 中散布度的最小值。保证最小值存在。答案对 998244353 取模。
可以证明答案可以写成互素的 qp,且 q≡0(mod998244353);输出 p⋅q−1mod998244353。
输入格式
第一行一个整数 t(1≤t≤2000)。
每组测试:
- 第一行两个整数 n,m(1≤n≤109,1≤m≤2000);
- 接下来 m 行,每行两个整数 li,ri(1≤li≤ri≤n)。
保证所有测试的 m 之和不超过 2000。
输出格式
每组测试输出一个整数,表示答案对 998244353 取模。
样例
输入:
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/2,499122178≡3⋅2−1(mod998244353)。