神鱼推题，必是好题。

前几天刚做过[BJOI2019]勘破神机，于是就会这题了。（BJ人民强啊……%鱼）

首先要求是

$$\sum\limits_{i=0}^nx^if_i$$

应该很明显能想到把 $f_i$ 写成通项公式。

$$f_i=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^i-(\dfrac{1-\sqrt{5}}{2})^i)$$

那么带进去：

$$\sum\limits_{i=0}^nx^i\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^i-(\dfrac{1-\sqrt{5}}{2})^i)$$

$$\dfrac{1}{\sqrt{5}}\sum\limits_{i=0}^nx^i((\dfrac{1+\sqrt{5}}{2})^i-(\dfrac{1-\sqrt{5}}{2})^i)$$

$$\dfrac{1}{\sqrt{5}}(\sum\limits_{i=0}^nx^i(\dfrac{1+\sqrt{5}}{2})^i)-\sum\limits_{i=0}^nx^i(\dfrac{1-\sqrt{5}}{2})^i))$$

$$\dfrac{1}{\sqrt{5}}(\sum\limits_{i=0}^n(\dfrac{1+\sqrt{5}}{2}\times x)^i-\sum\limits_{i=0}^n(\dfrac{1-\sqrt{5}}{2}\times x)^i)$$

扩个系，变成等比数列求和，做完了。

（貌似 $\color{black}{I}\color{red}{tst}$ 大爷用的矩阵快速幂直接切掉了？还是人家神啊……）

复杂度 $O(T\log n)$。

#include
      
       using namespace std;typedef long long ll;const int mod=1000000007,inv2=500000004,inv5=400000003;#define FOR(i,a,b) for(int i=(a);i<=(b);i++)#define ROF(i,a,b) for(int i=(a);i>=(b);i--)#define MEM(x,v) memset(x,v,sizeof(x))inline ll read(){    char ch=getchar();ll x=0,f=0;    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();    return f?-x:x;}int t,x;ll n;inline int add(int x,int y){
    return x+y
       
        >=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);    return ans;}struct comp{    int x,y;    comp(int xx=0,int yy=0):x(xx),y(yy){}    comp operator+(comp c){
    return comp(add(x,c.x),add(y,c.y));}    comp operator-(comp c){
    return comp(sub(x,c.x),sub(y,c.y));}    comp operator*(comp c){
    return comp(add(mul(x,c.x),mul(5,mul(y,c.y))),add(mul(x,c.y),mul(y,c.x)));}    comp inv(){        int t=qpow(sub(mul(x,x),mul(5,mul(y,y))),mod-2);        return comp(mul(x,t),sub(0,mul(y,t)));    }    comp operator/(comp c){
    return *this*c.inv();}    bool operator==(comp c){
    return x==c.x && y==c.y;}}A(inv2,inv2),B(inv2,mod-inv2),C(0,inv5);inline comp qpow(comp a,ll b){    comp ans(1,0);    for(;b;b>>=1,a=a*a) if(b&1) ans=ans*a;    return ans;}comp calc(comp x,ll n){    if(x==comp(1,0)) return n+1;    return (comp(1,0)-qpow(x,n+1))/(comp(1,0)-x);}int main(){    t=read();    while(t--){        n=read();x=read()%mod;        printf("%d\n",(C*(calc(A*comp(x,0),n)-calc(B*comp(x,0),n))).x);    }}