Fibs og Dibs

flickr.com에서 가져온 그림

모두가 알다시피, Dagur와 Elvar는 게이머이며 긴 게임을 즐겨 한다. 이제 그들은 두 번째로 좋아하는 게임인 Fibs와 Dibs를 하고 싶어 한다. 게임은 다음과 같이 진행된다. 먼저 Dagur가 정수 $a$을 고르고, 그다음 Elvar가 그보다 크거나 같은 또 다른 정수 $b$을 고른다. 마지막으로 플레이할 라운드 수인 $n$을 정한다.

각 라운드에서 Dagur는 먼저 Fibs''라고 외친다. 그러면 두 수를 더하고 Dagur가 새 수를 가져가므로, $a$에는 $a + b$의 값이 대입된다. 그다음 Elvar가 Dibs''라고 말하고 같은 단계를 반복하지만, 이번에는 Elvar가 새 수를 가져가므로, $b$에는 $a + b$의 값이 대입된다.

둘은 상당히 성급하고, 자신들이 가장 좋아하는 게임인 Dibs와 Fibs를 정말로 하러 가고 싶기 때문에 $n$라운드를 플레이하고 싶지 않다. 그래서 $n$라운드가 끝난 뒤 최종적으로 어떤 수를 갖게 되는지 알아내도록 여러분에게 도움을 요청한다.

채점

그룹 | 점수 | 제한 조건

1 | 20 | $0 \leq n \leq 10$

2 | 40 | $0 \leq n \leq 10^5$

3 | 40 | $0 \leq n \leq 10^{12}$

입력의 첫째 줄에는 Dagur가 고른 수인 정수 $a$와 Elvar가 고른 수인 $b$가 주어지며, $1 \leq a \leq b \leq 10^5$이다. 그다음 줄에는 Dagur와 Elvar가 플레이하려는 라운드 수인 정수 $n$이 주어진다.

Dagur와 Elvar가 최종적으로 갖게 되는 두 정수를 출력한다. 한 줄에 두 수를 공백으로 구분하여 출력한다. 먼저 Dagur가 최종적으로 갖게 되는 정수를 출력하고, 그다음 Elvar가 최종적으로 갖게 되는 정수를 출력한다. 수가 상당히 커질 수 있으므로, $10^9 + 7$로 나눈 나머지를 출력해야 한다.