Problem C
Fibs og Dibs
Languages
en
is
In each round Dagur start by calling “Fibs”, when he does that they add their two numbers together and Dagur takes the new number, so that $a$ takes the value of $a + b$. Then Elvar says “Dibs” and they repeat the steps, except now Elvar takes the new number, so that $b$ takes the value of $a + b$.
As they are quite impatient, they don’t want to play $n$ rounds, since they really want to go play their favourite game Dibs and Fibs. So they ask you to help them find out which numbers they will end up with after the $n$ rounds.
Input
The first line of the input contains two integers, $a$, the number that Dagur picks, and $b$ the number that Elvar picks. Then one line follows with one integer $n$, the amount of rounds Dagur and Elvar want to play.
Output
Output the two integers that Dagur and Elvar end up with. Output the numbers in one line sperated by a space, first the integer that Dagur ends with and then the integer that Elvar ends with. Since the numbers can become quite large, you should output them modulo $10^9 + 7$.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$0 \leq n \leq 10$ |
|
2 |
40 |
$0 \leq n \leq 10^5$ |
|
3 |
40 |
$0 \leq n \leq 10^{12}$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 2 |
10 16 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 2 10 |
17711 28657 |
