시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 128 MB 147 72 59 51.304%

문제

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을 골라 1 xor 2의 결과값인 3이 적힌 카드와 교체하는 경우를 제외하고 다른 경우는 존재하지 않는다.

출처

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