토끼 농장

농부 DongDong의 올해 작물 수확량은 계속 부진하다. 돈을 더 벌 방법을 고민하던 중, 옆집 아이들이 토끼 번식 이야기를 나누는 것을 우연히 들었다.

문제는 이렇다. 첫 달 초에 어린 토끼 한 쌍이 태어났다. 이 토끼들은 두 달을 자란 뒤, 세 번째 달 초부터 매달 새끼 토끼 두 마리를 낳는다. 새로 태어난 토끼도 두 달을 자라면, 그 뒤로 매달 한 쌍씩 새끼를 낳는다. 아이들은 $n$번째 달에 토끼가 모두 몇 쌍인지 묻는다.

눈치 빠른 독자라면 이미 알아챘을 것이다. $n$번째 달의 토끼 쌍 수는 $n$번째 피보나치 수와 같다. DongDong은 피보나치 수가 무엇인지 모르지만, 규칙은 알아냈다. 달 $i+2$의 토끼 쌍 수는 달 $i$의 쌍 수와 달 $i+1$의 쌍 수를 더한 것과 같다. 따라서 처음 몇 달의 토끼 쌍 수는 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 이다.

DongDong은 시간이 갈수록 토끼가 빠르게 늘어난다는 것을 알게 된다. 토끼 번식으로 큰돈을 벌 생각에, 첫 달 초에 바로 토끼 한 쌍을 샀다.

DongDong은 매일 토끼에게 먹이를 준다. 토끼는 먹는 습관이 매우 까다롭다. 항상 $k$쌍이 원을 이루어 둘러앉는다. $k$쌍에 못 미치는 나머지 무리는 따로 원을 이룬다. 토끼는 외로움을 몹시 싫어하기 때문이다. 세 번째 달부터, 먹이를 줄 때 한 쌍으로만 이루어진 원이 생기면 그 쌍은 곧 죽는다. 죽는 토끼는 항상 가장 나중에 태어난 토끼라고 가정한다. 예를 들어 $k=7$이면 처음 몇 달의 토끼 쌍 수는 1, 1, 2, 3, 5, 7, 12, 19, 31, 49, 80, ... 이다.

$n$이 주어질 때, $n$번째 달의 토끼 쌍 수를 구하라. 답이 매우 클 수 있으므로 $p$로 나눈 나머지를 구하면 된다.

세 개의 양의 정수 $n$, $k$, $p$가 한 줄에 주어진다.

$n$번째 달의 토끼 쌍 수를 $p$로 나눈 나머지를 한 줄에 출력한다.

• $1 \le n \le 10^{18}$
• $2 \le k \le 10^{6}$, $2 \le p \le 10^{9}$