题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6395
题目大意：

求F(n)%1e9+7

在构造系数矩阵的时候，int(p/n)是变化的，但是可以分块求和。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;

struct mat
{
    LL m[3][3];
};

mat msub(mat a, mat b, int n)
{
    mat ret;
    memset(&ret,0,sizeof(ret));
    for(int i=0;i<n;i++)
        for(int k=0;k<n;k++)
        {
            if(a.m[i][k]==0){
                continue;
            }
            for(int j=0;j<n;j++){
                ret.m[i][j]=(a.m[i][k]*b.m[k][j]%mod+ret.m[i][j])%mod;
            }
        }

    return ret;

}

void unit(mat &a, int n){
    for(int i=0 ;i<n; i++){
        a.m[i][i]=1;
    }
}

mat qpow(mat a,LL x, int n)//快速幂
{
    mat ans;
    memset(&ans, 0, sizeof(ans));
    unit(ans, n);//初始化
    while(x){
        if(x&1) ans=msub(ans,a, n);
        a=msub(a,a, n);
        x>>=1;
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        LL a, b, c, d, p, n;
        scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &p, &n);
        if(n==1){
            printf("%lld\n", a);
            continue;
        }
        if(n==2){
            printf("%lld\n", b);
            continue;
        }

        mat A;
        A.m[0][0]=d, A.m[0][1]=c, A.m[0][2]=1;
        A.m[1][0]=1, A.m[1][1]=0, A.m[1][2]=0;
        A.m[2][0]=0, A.m[2][1]=0, A.m[2][2]=1;

        for(int i=3; i<=n; i++){
            if(p/i==0){//特判
                mat t=A;
                t.m[0][2]=0;
                t=qpow(t, (LL)n-i+1, 3);
                b=(t.m[0][0]*b%mod+t.m[0][1]*a%mod+t.m[0][2]%mod)%mod;
                printf("%lld\n", b);
                break;
            }
            else{
                LL k=min(p/(p/i), (LL)n);
                mat t=A;
                t.m[0][2]=p/i;
                t=qpow(t, k-i+1, 3);
                LL s=(t.m[0][0]*b%mod+t.m[0][1]*a%mod+t.m[0][2]%mod)%mod;
                a=(t.m[1][0]*b%mod+t.m[1][1]*a%mod+t.m[1][2]%mod)%mod;
                b=s;
                i=k;
                if(k==n){
                    printf("%lld\n", b);
                    break;
                }
            }
        }
    }

    return 0;
}