AT_kupc2017_k Xor Summation Pattern

[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_k 整数 $ n $, $ m $, $ k $ が入力として与えられます。このとき、以下の条件を満たす長さ $ n $ の数列 $ s $ の個数を $ 10^9\ +\ 7 $ で割った余りを求めてください。 1. $ s_i $ $ (1\ \leq\ i\ \leq\ n) $ は $ 0 $ 以上 $ m $ 以下の整数である。 2. $ 0\ xor\ s_1\ xor\ s_2\ xor\ ...\ s_n\ =\ k $ である。ただし、$ xor $ はビットごとの[排他的論理和](https://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C#.E3.83.93.E3.83.83.E3.83.88.E3.81.94.E3.81.A8.E3.81.AE.E6.8E.92.E4.BB.96.E7.9A.84.E8.AB.96.E7.90.86.E5.92.8C "排他的論理和")を表すものとする。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ k $

問題文の条件を満たす数列 $ s $ の個数を $ 10^9\ +\ 7 $ で割った余りを出力せよ。

### 制約 - $ n $, $ m $, $ k $ は整数である。 - $ 0\ \leq\ n,\ m,\ k\ \leq\ 10^{18} $ ### Sample Explanation 1 長さが $ 0 $ の数列は $ 1 $ 通りです。このときこの数列は条件 $ 2 $ も満たします。 ### Sample Explanation 3 以下の $ 6 $ 通りの数列が存在します。 - { $ 0 $, $ 1 $, $ 2 $ } - { $ 0 $, $ 2 $, $ 1 $ } - { $ 1 $, $ 0 $, $ 2 $ } - { $ 1 $, $ 2 $, $ 0 $ } - { $ 2 $, $ 0 $, $ 1 $ } - { $ 2 $, $ 1 $, $ 0 $ }