#P1000. 斐波那契数列

斐波那契数列

当前没有测试数据。

斐波那契数列

题目描述

大家都知道,斐波那契数列是满足如下性质的一个数列:

f1=1f_1 = 1

f2=1f_2 = 1

fn=fn1+fn2f_n = f_{n-1} + f_{n-2} (n2n \geq 2nn 为整数)

请你求出 fnmodpf_n \mod p 的值。

输入格式

  • 第 1 行:一个整数 nn
  • 第 2 行:一个整数 pp

输出格式

  • 第 1 行:fnmodpf_n \mod p 的值。

样例 #1

样例输入 #1

5
1000000007

样例输出 #1

5

样例 #2

样例输入 #2

10
1000000007

样例输出 #2

55

提示

对于 100%100\% 的数据,n1015,p<231n \leq 10^{15}, p<2^{31}

统计

相关

在以下作业中: