SUM-XOR Equation 2

2 secs 1024 MB
YSatUT

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

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

問題文


以上の自然数つの非負整数が与えられるので、を満たす非負整数列の個数をで割った余りを求めて下さい。ただし、は排他的論理和を意味します。

制約


  • 入力は全て整数

入力


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

n p q

出力


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

サンプル


入力1
2 5 1
出力1
2

前の問題のテストケース1より、解はなので、通りとなります。


入力2
2 1 0
出力2
0

条件を満たすは存在しません。


入力3
100 100 0
出力3
674414329

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

提出


Go (1.14)