시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 128 MB38517816046.243%

문제

chogahui05는 xor 게임을 하고 있다. 이 게임은 n개의 턴 동안 진행되며, 정수 0 ~ 231 - 1가 적혀있는 무한히 많은 카드를 가지고 진행하는 재밌는 게임이다. 이 게임의 규칙은 다음과 같다.

  • chogahui05는 처음에 정수 a가 적힌 카드를 가지고 시작한다. 
  • 매 턴마다, chogahui05는 아래와 같은 작업을 수행해야 한다.
  • 0 ≤ u < 231을 만족하는 정수 u를 하나 고른다.
  • 현재 가지고 있는 카드를 num이라고 했을 때, 현재 가지고 있는 카드를 num (xor) u의 결과값이 적힌 카드로 교체한다.

게임을 마치고, chogahui05가 들고 있는 카드에 적혀 있는 수는 b가 되었다.

이때 게임의 과정으로 가능한 경우의 수를 1000000007(109 + 7)로 나눈 나머지를 출력하라.

입력

첫째 줄에 정수 a, b (0 ≤ a, b < 231), n(0 < n ≤ 109)이 공백으로 구분되어 주어진다. 

출력

Chogahui05가 가지고 있던 정수 a가 적힌 카드가 게임이 끝나고 b가 적힌 카드가 되었을 때, 게임의 과정으로 가능한 경우의 수를 1000000007(109 + 7)로 나눈 나머지를 출력하라.

예제 입력 1

2 3 1

예제 출력 1

1

힌트

chogahui05는 처음에 2가 적혀져 있는 카드를 가지고 있다. 첫 번째 턴에 정수 u로 1을 골라 2 xor 1의 결과값인 3이 적힌 카드와 교체하는 경우를 제외하고 다른 경우는 존재하지 않는다.

출처

Contest > BOJ User Contest > 네블컵 > 제1회 네블컵 D번