OFF-ZERO Sequence (Easy)

2 secs 1024 MB
bayashiko

問題文


以下の条件を全て満たす数列は何通り存在するでしょうか?で割った余りを求めてください。
・要素数は個以上個以下である。
・各要素は全て非負整数である。
・各要素は以上未満である。
なる任意の正整数の組について、がともに存在するならば、である。ただし、ここではbitごとの排他的論理和を表す。
なお、2つの数列が異なるとは、の要素数が異なる、またはとなるような正整数が存在することを指します。

制約


・入力は全て整数である。

入力


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

A B K

出力


条件を全て満たすような数列の個数をで割った余りを出力してください。

入力例1


8 62 0 

出力例1


55

のみからなる要素数の計個の数列が条件を満たします。

入力例2


41 82 69

出力例2


116525415

提出


Go (1.14)