又来补之前做的题了。。
容易发现第(i)关为奖励关卡当且仅当(operatorname{bitcount}(i))为奇数。
于是考虑暴力dp，(f_{i,j,0/1})为([0,2^i))位置中(a/b)关卡编号的(j)次方和。
[f_{i,j,k}=f_{i-1,j,k}+sum_{l=0}^jinom{j}{l}f_{i-1,l,1-k}2^{(i-1)(j-l)}
]
因为每次加入最高位(2^i)会导致(operatorname{bitcount})奇偶性翻转，编号统一加(2^i)，二项式定理暴力展开即可。
考虑类似数位DP的东西，对于每个(n)上的(1)，假定这是第一个把(1)变成(0)的位置求总和。就是每次要求([s,s+2^i))的答案。
考场上就想到这了。。然后在个位特判翻了傻逼错误导致暴力写挂，我真是个人才哈哈
我们要学习noi主斗地大力猜结论的精神，当(i > j)时有(f_{i,j,k}=dfrac{sum_{k=0}^{2^i-1}k^j}{2})
对于(i le K)使用上述暴力DP，(i > K)用上述定理插值求解
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar(x%10+'0');
}
const int mod=1e9+7;
inline void tmod(int &x){x%=mod;}
inline int qpow(int a,int b){
int res=1;a%=mod;
for(;b;b>>=1,tmod(a*=a))
if(b&1)tmod(res*=a);
return res;
}
inline int ginv(int x){return qpow(x,mod-2);}
inline int norm(int x){return (x%mod+mod)%mod;}
int C[510][510],dp[510][510][2],K,a[510],len,pw2[500010],sum[500010],Y[510];
char s[500010];
inline int calc(int x){
int ss=0;
fp(i,0,K+1){
Y[i]=ss;
int t=0;
fd(j,K,0)tmod(t=t*i+a[j]);
tmod(ss+=t);
}
int ans=0;
fp(i,0,K+1){
int t=Y[i],p=1;
fp(j,0,K+1)if(i!=j){
tmod(t*=x-j);tmod(p*=i-j);
}
tmod(ans+=t*ginv(p));
}
return ans;
}
main(){
scanf("%s",s);len=strlen(s)-1;reverse(s,s+len+1);
fp(i,0,len)s[i]-='0';
K=read()-1;
fp(i,0,K)a[i]=read();
pw2[0]=1;fp(i,1,500000)pw2[i]=pw2[i-1]*2%mod;
fp(i,0,K){
C[i][0]=1;
fp(j,1,i)tmod(C[i][j]=C[i-1][j]+C[i-1][j-1]);
}
fp(j,0,K)dp[0][j][1]=1;dp[0][0][0]=1;
fp(i,1,K)fp(j,0,K)fp(l,0,1){
dp[i][j][l]=dp[i-1][j][l];
fp(p,0,j)tmod(dp[i][j][l]+=dp[i-1][p][l^1]*C[j][p]%mod*pw2[i*(j-p)]);
}
fd(i,len,0)sum[i]=sum[i+1]^s[i];
int ans=0,t=0;
fp(i,K+1,len)if(s[i])tmod(t+=pw2[i]);
fd(i,min(K,len),1)if(s[i]){
fp(j,0,K){
int p=1;
fp(l,0,j){
tmod(ans+=p*dp[i-1][j-l][sum[i+1]^1]%mod*C[j][l]%mod*a[j]);
tmod(p*=t);
}
}
tmod(t+=pw2[i]);
}//枚举第一个没有顶上去的1
if(s[0]&&(sum[1]&1)){
int p=1;
fp(j,0,K){
tmod(ans+=a[j]*p);
tmod(p*=t);
}
}
t=0;
fp(i,K+1,len)if(s[i])tmod(t+=pw2[i]);
printf("%lld
",norm(ans+(mod+1)/2*calc(t)));
return 0;
}