SUM-XOR Equation 2

2 secs 1024 MB
YSatUT's icon YSatUT

注:前の問題を解いていない方は、こちらより先に前の問題を解くことをお勧めします。

また、Pythonなどの遅い言語では想定解でもTLEする可能性があります。

問題文

22以上の自然数nn22つの非負整数p,qp,qが与えられるので、{a1+a2++an=pa1a2an=q\left\{\begin{array}{l}a_1+a_2+\cdots+a_n=p \\ a_1\oplus a_2\oplus\cdots\oplus a_n=q \end{array}\right.を満たす非負整数列{a1,a2,an}\left\{a_1,a_2,\cdots a_n\right\}の個数を998244353998244353で割った余りを求めて下さい。ただし、\oplusは排他的論理和を意味します。

制約

  • 2n1052\leq n\leq 10^5
  • 0p,q<2600\leq p,q<2^{60}
  • 入力は全て整数

入力

入力は以下の形式で与えられます。\\

n p q

出力

答えを1行に出力して下さい。

サンプル

入力1
2 5 1
出力1
2

前の問題のテストケース1より、解は(a1,a2)=(2,3),(3,2)(a_1,a_2)=(2,3),(3,2)なので、22通りとなります。


入力2
2 1 0
出力2
0

条件を満たす{a1,a2}\left\{a_1,a_2\right\}は存在しません。


入力3
100 100 0
出力3
674414329

998244353998244353で割った余りを求めて下さい。

Submit


Go (1.21)