Calculate Fibonacci n-th term modulo m
Fibonacci sequence is defined by obtaining each next term in the sequence by adding up the previous two, while the first two elements are 0 and 1:
Given the number
n, you are asked to calculate the n-th Fibonacci numbers modulo m.As we’re only interested in the result modulo
m, the value of n can be very large.Input
The only line of the input contains two integers
n (0 ≤ n ≤ ) and m (1 ≤ m ≤ 50).Output
The program should print the result of
Examples
Input | Output |
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Explanation
- fib(0) = 0 ⇒ 0 mod 5 = 0
- fib(1) = 1 ⇒ 1 mod 5 = 1
- fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
As we’re calculating the fibonacci numbers modulo
m, and the next number always depends on the previous two, the numbers start to repeat at some point. You can try printing many values modulo m and notice the pattern after which they start repeating.Hint 2
As the numbers start repeating at some point, you can directly calculate the
n-th Fibonacci number instead of looping through all of them.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB