Dasha also Fibonaccis#5715
- Mom, mom, why is each quarter on the clock 15 minutes?
- Ask Vasya, it seems Fibonacci explained it to him, and I have to go!
From a morning conversation between a daughter and her mother
Dasha, who is in the ninth grade, is one year older than eighth-grader Vasya and is also fascinated by Fibonacci numbers. Since Dasha is older, the problems she solves are more challenging. Now she is interested in the following question: how can you quickly find the product of the last digits of the -th Fibonacci number? Unlike Vasya, if the answer has fewer than three digits, Dasha does not prepend any extra leading zeros.
Recall that the Fibonacci numbers are defined by the following recurrence relations:
At the same time, Dasha also wonders about something else: Why did her mom answer like that, and is her answer in any way related to the problem that Dasha is working on?
Each line of the input contains a single integer (0 \leq k \leq 9223372036854775807).
For each test case in the input, print on a separate line a single number—the answer to the problem.
Example 1