$\newcommand{\align}[1]{\begin{align*}#1\end{align*}}$题意：对于一个序列$a_{1\cdots n}(a_i\in[1,2^k-1])$，定义序列$b_{1\cdots n}$满足$b_i=a_1|\cdots|a_i$，这里的“$|$”是按位或，问有多少种可能的$a_{1\cdots n}$使得$b_{1\cdots n}$严格单调递增

首先，$a$每增加一个数，这个数必须有一个二进制位是前面所有数都没有出现过的，所以当$n\gt k$时是没有解的，那个$n\leq10^{18}$是在吓人

然后考虑DP，设$f_{i,j}$为$a$有$i$个数且这些数的或占了$j$个二进制位（占位不考虑顺序），那么答案为$\align{\sum\limits_{i=n}^k\binom kif_{n,i}}$（统计答案的时候就要考虑顺序了）

考虑如何转移，我们有$\align{f_{x+y,i}=\sum\limits_{j=0}^i\binom ijf_{x,j}\left(2^j\right)^yf_{y,i-j}}$（前$x$个数占据哪$j$位，后$y$个数必须占$i-j$位，后$y$个数的其他$j$位可以随便取），整理一下得到$\align{\dfrac{f_{x+y,i}}{i!}=\sum\limits_{j=0}^i\dfrac{f_{x,j}2^{yj}}{j!}\dfrac{f_{y,i-j}}{(i-j)!}}$，这是卷积的形式，并且第一维下标也是相加的形式，所以可以直接快速幂+FFT求得答案

可是模数是$10^9+7$...毒瘤出题人

所以学习了一发拆系数FFT：在模$p$意义下，我们可以选取一个$M\geq\left\lceil\sqrt p\right\rceil$，并且把每个系数表达为$aM+b$的形式（这时$a,b\leq M$，因为数字变小了所以爆精度的风险低一些），把每个多项式拆成两个多项式，稍微推下式子就可以做到用$7$次FFT完成任意模数卷积，注意合并系数时适当模一下防止爆$\text{long long}$

然后就做完了，感觉此题略神==

#include
     
      #include
      
       #include
       
        typedef long long ll;typedef double du;const int mod=1000000007;int mul(int a,int b){return a*(ll)b%mod;}int pow(int a,int b){	int s=1;	while(b){		if(b&1)s=mul(s,a);		a=mul(a,a);		b>>=1;	}	return s;}struct complex{	du x,y;	complex(du a=0,du b=0){x=a;y=b;}};complex operator+(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}void swap(complex&a,complex&b){	complex c=a;	a=b;	b=c;}int rev[65536],N;complex w[16][65536];void pre(int n){	int i,j,k;	for(N=1,k=0;N
        
         <<=1)k++;	for(i=0;i
         
          >1]>>1)|((i&1)<<(k-1));	k=0;	for(i=2;i<=N;i<<=1){		for(j=0;j
          
           >1;k++){ wi=w[f][k]; wi.y*=on; t=wi*a[i/2+j+k]; a[i/2+j+k]=a[j+k]-t; a[j+k]=a[j+k]+t; } } f++; } if(on==-1){ for(i=0;i
           
            >15; B[i]=a[i]&32767; C[i]=b[i]>>15; D[i]=b[i]&32767; } fft(A,1); fft(B,1); fft(C,1); fft(D,1); for(i=0;i
            
             k){ putchar('0'); return 0; } fac[0]=1; for(i=1;i<=k;i++)fac[i]=mul(fac[i-1],i); rfac[k]=pow(fac[k],mod-2); for(i=k;i>0;i--)rfac[i-1]=mul(rfac[i],i); for(i=1;i<=k;i++)f[i]=rfac[i]; g[0]=1; pre(k<<1|1); b=2; while(n){ if(n&1)trans(g,f,k,b); trans(f,f,k,b); b=mul(b,b); n>>=1; } ans=0; for(i=n;i<=k;i++)ans=(ans+mul(mul(g[i],fac[i]),binom(k,i)))%mod; printf("%d",(ans+mod)%mod);}