U703133 惊鹊
题目背景
https://music.163.com/song?id=1840749937
题目描述
惊鹊很好听，不管你听没听，忘川风华录发现了 $T$ 组加密数据，设斐波那契数列 $\{F_n\}$，给出 $n,m,d$，明文根据下式得出：
$$
\sum_{i=0}^{n-1}F_{d-1}^iF_{(n-i-1)d+1}\pmod m
$$
你需要求出这个明文。
输入格式
无
输出格式
无
说明/提示
对于所有的数据，有：$1\leq T\leq10^5,1\leq n,d,m\leq 10^9$
题解：https://www.cnblogs.com/Simazhiyinzhui/p/21467881