The Pell numbers are defined by P(0) = 0, P(1) = 1, and P(k) = 2*P(k-1) + P(k-2) for k >= 2.
Given n and m, output P(n) mod m. Note that n can be extremely large, so the recurrence cannot simply be unrolled step by step within the time limit for the largest inputs.
Line 1: two space-separated integers n and m.
A single integer: P(n) mod m.
Example 1
Input
5 1000
Expected
29
Explanation
P(0..5) = 0,1,2,5,12,29, so P(5) mod 1000 = 29.
Example 2
Input
0 7
Expected
0
Explanation
P(0) = 0, and 0 mod 7 = 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →