피보나치수열의 합

피보나치수열이란 앞의 두 수를 더하여 나오는 수열이다.

첫 번째 수와 두 번째 수는 1이고 세 번째 수는 첫 번째 수와 두 번째 수를 더하여 2가 된다.

피보나치수열을 첫 번째 수부터 나열해 보면 다음과 같다.

1, 1, 2, 3, 5, 8, 13 ...

자연수 N과 M을 입력받아 N번째 수 까지의 피보나치 수의 합을 구하여

M으로 나눈 나머지를 출력하는 프로그램을 작성하여라.

※ a, b, mod가 양의 정수, a^b = a의 b제곱 이라고 할 때,

나머지 연산에 관하여 다음과 같은 성질이 있다고 한다.

(a + b) % mod = (a % mod + b % mod) % mod

(a - b) % mod = (a % mod - b % mod ) % mod = (a % mod - b % mod + mod) % mod

(a * b) % mod = (a % mod * b % mod) % mod

(a^b % mod) = (a % mod) ^ b % mod

입력

첫 행에 N(1 <= N <= 1,000,000)과 M(1 <= N <= 1,000,000,007)이 공백으로 구분되어 입력된다.

출력

하나의 행에 N번째 까지의 피보나치 수의 합을 구하여 M으로 나눈 나머지를 출력한다.

예제

태그

출처

comkiwer

피보나치수열의 합 1s 64MB