xor game

chogahui05 plays an xor game. The game runs for $n$ turns, and there is an unlimited supply of cards for every integer from $0$ to $2^{31} - 1$. The rules are the following.

• chogahui05 starts holding the card with the integer $a$ on it.
• On every turn chogahui05 must do the following.
  • Pick one integer $u$ with $0 \le u < 2^{31}$.
  • Let $num$ be the number on the card currently held. Replace that card with the card that has $num \oplus u$ on it. Here $\oplus$ is the bitwise exclusive or.

When the game ended, the number on the card chogahui05 held was $b$.

Find the number of possible game processes modulo $1000000007$ ($10^9 + 7$). Two processes are different when the integer $u$ picked on some turn is different.

The first line contains the integers $a$, $b$ ($0 \le a, b < 2^{31}$) and $n$ ($0 < n \le 10^9$), separated by spaces.

Print on the first line the number of possible game processes modulo $1000000007$.

Take $a = 2$, $b = 3$, $n = 1$. There is only one turn, so the only possibility is picking $u = 1$ and replacing the card with the one that has $2 \oplus 1 = 3$ on it.