#P1606. 斐波那契数列

斐波那契数列

斐波那契数列

题目背景

斐波那契数列(Fibonacci sequence),又称黄金分割数列 ,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称“兔子数列”,其数值为:1、1、2、3、5、8、13、21、34……在数学上,这一数列以如下递推的方法定义:F(0)=1,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)。

(以上内容来自百度百科)

由于斐波那契数列后面的数字很大,今年是 2024 年,所以小季想研究斐波那契数列模2024的结果。

题目描述

为了方便计算,我们记斐波那契数列为 ff,它的递推式为

  • f1=1f_1 = 1
  • f2=1f_2 = 1
  • fn=fn1+fn2f_n = f_{n-1} + f_{n-2} (n2n \ge 2nn 为整数)

请求出 fn mod pf_n \ mod \ p , p=2024p = 2024 的值,由于 nn 的值可能非常大,我们使用幂指数的形式来表示,即 n=abn = a^b.

输入格式

输入包括多组数据。

第一行一个整数 TT,代表数据组数。

接下来 TT 行,每行两个整数 aabb,用空格隔开,含义见描述。

输出格式

对于每组数据,输出一行结果,代表 fnmod 2024=fabf_n mod \ 2024 = f_{a^b} mod 2024mod \ 2024 的值。

样例输入

4
4 1
3 2
2 6
2024 2024

样例输出

3
34
619
987

数据范围及约定

测试点编号 约定
151 \sim 5 1ab10241 \le a^b \le 1024
6106 \sim 10 1ab1091 \le a^b \le 10^9
112011 \sim 20 1a,b1091 \le a, b \le 10^9

对于所有数据, 1T1001 \le T \le 100