Problem5144--组合数前缀和

5144: 组合数前缀和

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有T 组询问,每次询问给出两个数 n,m,满足$0 \leqslant m \leqslant n$,你需要求出$\sum_{i=0}^{m}C(n,i)$。
由于这个数可能很大,你只需要求出这个值 $mod \; 998244353$ 后的结果。

Input

第一行一个正整数 T,表示询问个数。 接下来 T 行每行两个非负整数 n,m,表示一组询问。

Output

T 行每行一个 [0, 998244352] 的正整数,表示对应询问的答案。

Sample 1 Input

5
100000 23333
100000 98765
666623333 233336666
123456789 98765432
900000000 233333

Sample 1 Output

780149589
470308993
115424175
217983531
61569534

HINT

【数据范围】
共有个 10 测试点,前 2 个测试点满足 $T \leqslant 10, n\leqslant 10^{5}$。
第 i ($i \geqslant 3$)个测试点满足 $T = i-2, n\leqslant 9\ast 10^{8}$。m 在 $[0, n]$ 均匀随机。

Source/Category

基础算法 4.2.前缀和