Twilight Sparkle's Magical Research
Output: Standard Output (stdout)
Memory limit: 20 megabytes
Time limit: 0.5 seconds
While experimenting with her spells, Twilight Sparkle noticed something peculiar: she would often end up with more ingredients than she started with.
For example, if she casts the Boulanger spell on u ukuleles and v vuvuzelas, she would end up with 2u + 3v ukuleles and 5u + v vuvuzelas afterward.
This effect can stack: if she casts Boulanger again, she'll have 2(2u + 3v) + 3(5u + v) = 19u + 9v ukuleles and 5(2u + 3v) + (5u + v) = 15u + 16v vuvuzelas.
In general, a spell can transform u ukuleles and v vuvuzelas into Au + Bv ukuleles and Cu + Dv vuvuzelas, where A, B, C, and D are constants specific to the spell.
Help Twilight figure out how many ukuleles and vuvuzelas she would have, given the specification for a spell and the number of times she casts it. Assume that she starts with 1 ukulele and 1 vuvuzela. (Whether that is a good idea or not is out of scope for this task.)
The first line will contain four space-separated integers, 0 \le A, B, C, D < 10^4, which specify the spell.
The second line will contain one integer, 0 \le N < 10^9. This is the number of times Twilight wants to cast the spell.
Output two space-separated integers: the final number of ukuleles and vuvuzelas, respectively.
As these numbers can be large, you must only output the last 4 digits of each number. For example, if the answer is 987654321, output 4321 instead.
- Subtask 1 (25%): N \le 1000, and the final number of ukuleles and vuvuzelas is below 10^4.
- Subtask 2 (25%): N \le 10^5.
- Subtask 3 (50%): No restrictions.
Twilight Sparkle starts with 1 ukulele and 1 vuvuzela.
After casting the spell once, she has 2 \cdot 1 + 3 \cdot 1 = 5 ukuleles and 5 \cdot 1 + 1 \cdot 1 = 6 vuvuzelas.
After casting the spell twice, she has 2 \cdot 5 + 3 \cdot 6 = 28 ukuleles and 5 \cdot 5 + 1 \cdot 6 = 31 vuvuzelas.
After casting the spell three times, she has 2 \cdot 28 + 3 \cdot 31 = 149 ukuleles and 5 \cdot 28 + 1 \cdot 31 = 171 vuvuzelas.
Sample Input 1
2 3 5 1 3
Sample Output 1