话说这题TLE了n次，我就知道是输入输出问题，刚开始真心相当无奈（套用大牛代码也TLE），后来突然想起来改用C++提交，怒AC。。。（看来大牛平常也用C++提交啊！g++就是一个坑爹编译器.....)
公式推出来很简单，根据题意，F(n)=F(n-1)+2F(n-2)+...+nF(1)+1，试了几组测试数据发现F(n)和兔子数列有关，F(N)是兔子数列的第n-1项，有此得F(n)=3F(n-1)-F(n-2)，后来通过最初的公式推导出了这个。。。果断用矩阵快速幂推，发现超时，这是突然看到数据量很大，果断想到了斐波那契模一个数的循环问题。。现在就这个问题证明一下：若斐波那契数列模一个数存在循环节，则循环节必从1开始，且循环最后的两个数必是1和0。。。证明用反证法：若循环节不在第一位，设F(x)=f(y),f(x+1)=f(y+1)，则可以证明F(x-1)=f(y-1)，与之前假设F(x-1)!=f(y-1)不符合，所以循环一定在第一个，也就推出循环后两个数是1和0。。。初始化的时候，用F(n)=3f(n-1)-f(n-2)初始化，循环节折半为75000，代码略