xor 게임

chogahui05가 xor 게임을 한다. 게임은 $n$번의 턴 동안 진행하고, $0$부터 $2^{31} - 1$까지의 정수가 하나씩 적힌 카드가 종류마다 무한히 많이 준비되어 있다. 규칙은 다음과 같다.

• chogahui05는 정수 $a$가 적힌 카드를 들고 시작한다.
• 매 턴마다 아래 작업을 해야 한다.
  • $0 \le u < 2^{31}$을 만족하는 정수 $u$를 하나 고른다.
  • 지금 들고 있는 카드에 적힌 수를 $num$이라고 할 때, 그 카드를 $num \oplus u$가 적힌 카드로 바꾼다. $\oplus$는 비트 단위 배타적 논리합이다.

게임을 마쳤을 때 chogahui05가 들고 있는 카드에 적힌 수는 $b$였다.

게임의 과정으로 가능한 경우의 수를 $1000000007$($10^9 + 7$)로 나눈 나머지를 구하라. 어떤 턴에서 고른 $u$가 하나라도 다르면 서로 다른 과정이다.

첫째 줄에 정수 $a$, $b$ ($0 \le a, b < 2^{31}$)와 $n$ ($0 < n \le 10^9$)이 공백으로 구분되어 주어진다.

첫째 줄에 게임의 과정으로 가능한 경우의 수를 $1000000007$로 나눈 나머지를 출력한다.

$a = 2$, $b = 3$, $n = 1$인 경우를 보자. 턴이 한 번뿐이므로 $u$로 $1$을 골라 $2 \oplus 1 = 3$이 적힌 카드로 바꾸는 경우 말고는 없다.