注:前の問題を解いていない方は、こちらより先に前の問題を解くことをお勧めします。
また、Pythonなどの遅い言語では想定解でもTLEする可能性があります。
問題文
2以上の自然数nと2つの非負整数p,qが与えられるので、{a1+a2+⋯+an=pa1⊕a2⊕⋯⊕an=qを満たす非負整数列{a1,a2,⋯an}の個数を998244353で割った余りを求めて下さい。ただし、⊕は排他的論理和を意味します。
制約
- 2≤n≤105
- 0≤p,q<260
- 入力は全て整数
入力
入力は以下の形式で与えられます。
出力
答えを1行に出力して下さい。
サンプル
前の問題のテストケース1より、解は(a1,a2)=(2,3),(3,2)なので、2通りとなります。
条件を満たす{a1,a2}は存在しません。
998244353で割った余りを求めて下さい。