题目描述

给定一个整数 $K$，定义一个数列 $F_i$ 如下：

• $F_0=1$
• 如果 $i < K$，那么 $F_i=F_{i-1}+F_{i-2}+F_{i-3}+\dots+F_{0}$
• 如果 $i \geq K$，那么 $F_i=F_{i-1}+F_{i-2}+F_{i-3}+\dots+F_{i-K}$

给定两个整数 $N$ 与 $M$，输出 $F_N\bmod M$。

输入格式

• 单独一行：表示三个整数：$K$、$N$ 与 $M$

输出格式

2 5 10

8

样例解释 1

F0=1 F1=1 F2=2 F3=3 F4=5

数据范围

• $50\%$ 的数据，$1\leq K,N\leq 1,000$
• $100\%$ 的数据，$1\leq K,N\leq 1,000,000$
• $1\leq M\leq 2,000,000,000$