用N个不同的字符（编号1 - N），组成一个字符串，有如下要求：
(1) 对于编号为i的字符，如果2 * i > n，则该字符可以作为结尾字符。如果不作为结尾字符而是中间的字符，则该字符后面可以接任意字符。
(2) 对于编号为i的字符，如果2 * i <= n，则该字符不可以作为结尾字符。作为中间字符，那么后面接的字符编号一定要 >= 2 * i。
问有多少长度为M且符合条件的字符串，由于数据很大，只需要输出该数Mod 10^9 + 7的结果。
例如：N = 2，M = 3。则abb, bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。
Input
输入2个数，N, M中间用空格分割，N为不同字符的数量，M为字符串的长度。(2 <= N <= 10^6, 2 <= M <= 10^18)
Output
输出符合条件的字符串的数量。由于数据很大，只需要输出该数Mod 10^9 + 7的结果。
想半天不会做然后跑去瞄题解。。
首先，一个合法的字符串显然是由若干个合法的“链”组成的。
链的定义就是：从一个字母开始连，后面每个字母编号必须大于等于前一个的2倍，这样尽可能的连接下去。
所谓尽可能连接下去的意思是，链的最后一个字母编号i必须满足2 * i > n ，这样后面不能接东西了，并且只有这样的链才合法。
对于每个合法字符串，划分成合法链的方法是唯一的。
那么因为n不大，所以链的最大长度也很小...
设f[i][j]表示长度为i的链，链末尾编号为j的方案数。这个可以直接算出来，也就可以得到g[i]表示长度为i的链的所有方案数。
设ans[i]表示长度为i的合法字符串数，那么ans[i]=sum{ ans[i-x]*g[x] },1<=x<=链的最大长度。这个直接矩乘。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
//#define d double
#define ld long double
const int maxn=,modd=;
struct mat{int mp[][];}a,c;
int f[][maxn],af[][maxn];
int i,j,k,n,m,n1,len; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while(rx<''&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;
} inline void MOD(int &x){if(x>=modd)x-=modd;} mat operator *(mat a,mat b){
mat c;register int i,j,k;
for(i=;i<=len;i++)for(j=;j<=len;j++)for(c.mp[i][j]=,k=;k<=len;k++)
c.mp[i][j]=(c.mp[i][j]+1ll*a.mp[i][k]*b.mp[k][j])%modd;
return c;
}
int main(){ll m;
n=read(),scanf("%lld",&m);
for(i=;(<<i)<=n;i++);len=i,n1=n>>; for(i=n;i;i--)f[][i]=i>n1,af[][i]=af[][i+]+f[][i];
a.mp[][]=af[][];//printf(" %d\n",af[0][1]); bool now=,pre=;int premx=n;
for(i=;i<=len;i++,std::swap(now,pre)){
premx>>=,af[now][premx+]=;
for(j=premx;j;j--)MOD(af[now][j]=af[now][j+]+(f[now][j]=af[pre][j<<]));//,printf("%d %d f:%d\n",i,j,f[now][j]);
a.mp[][i]=af[now][];
}
for(i=;i<=len;i++)a.mp[i][i-]=;
for(i=;i<=len;i++)c.mp[i][i]=; while(m){
if(m&)c=c*a;
if(m>>=)a=a*a;
}
printf("%d\n",c.mp[][]);
}