F - n!+(n+1)!+(n+2)!
Earlgray
3
s
1024
MB
700
点
問題文
非負整数 $N$, $A$ が与えられます。次の式を満たす整数 $0 \leq n < 2^N$ の個数を $998244353$ で割った余りを求めてください。
$\mathrm{ord}_2(n! + (n + 1)! + (n + 2)!) = n - A$
ただし、正の整数 $m$ に対して、$\mathrm{ord}_2(m)$ で $m$ が $2$ で割り切れる回数の最大値を表します。
また、非負整数 $k$ に対して、$k!$ で $k$ の階乗を表します（$0! = 1$）。
$T$ 個のテストケースについて答えてください。
制約
- $1 \le T \le 20$
- $0 \leq N \leq 10^8$
- $0 \leq A \leq 10^5$
- 入力全ては整数
入力
入力は、以下の形式で標準入力から与えられる。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$
各ケースは以下の形式で与えられる。
$N$ $A$
出力
$T$ 行出力してください。
$i$ 行目には、$i$ 番目のテストケースの答えを出力してください。
入力例 1
3
4 2
0 0
100000000 100000
出力例 1
3
0
995555299
1番目のクエリについて、
$\mathrm{ord}_2(n! + (n + 1)! + (n + 2)!) = n - 2$
を満たす整数 $0 \le n < 16$ の個数を数え上げることになります。
例えば $n = 5$ のとき、
$\mathrm{ord}_2(n! + (n + 1)! + (n + 2)!) = \mathrm{ord}_2(5880) = 3 = n - 2$
となるため条件を満たします。
$n = 3, 5, 9$ の場合のみ条件を満たすことが分かるため、$3$ と出力します。
$998244353$ で割った余りを答えることに注意してください（3番目のクエリ参照）。