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.
Input format
Line 1: two space-separated integers n and m.
Output format
A single integer: P(n) mod m.
Constraints
- 0 <= n <= 1000000000000000000
- 1 <= m <= 1000000000