Rt，刚超过 1s 一直卡不过去，本机只用 900 ms

/*
    Author : SharpnessV & SharpnessX & 7KByte
    Right Output ! & Accepted !
*/
#include<cstdio>
//#include<atcoder/all>
//#define int long long

#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define pre(i, a, b) for(int i = (a);i >= (b);i--)
#define rp(i, a) for(int i = 1; i <= (a); i++)
#define pr(i, a) for(int i = (a); i >= 1; i--)

#define pc putchar
#define gc getchar
#define el putchar('\n')

typedef long long LL;
char buf[1<<22],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T> inline void read(T &x) {
    x = 0;bool flag = false; char ch = getchar();
    while (ch < '0' || ch > '9')flag = ch == '-' ? true : false, ch = getchar();
    while (ch >= '0' && ch <= '9')x = (x << 3) + (x << 1) + (ch & 15), ch = getchar();
    if(flag) x = -x;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args){read(t);read(args...);}
#define P 1000000007
template<typename T> void ad(T &x, int y) {x += y; if(x >= P) x -= P;}
template<typename T> void su(T &x, int y) {x -= y; if(x < 0) x += P;}
int Pow(int x, int y){
	int now = 1 ;
	for(; y; y >>= 1, x = 1LL * x * x % P)if(y & 1) now = 1LL * now * x % P;
	return now;
}

/***************************************************************************************************************************/
/*                                                                                                                         */
/***************************************************************************************************************************/
#define N 500005
#define M 505
int f[2][M][M], n, k, a[M], c[M][M], pw[N], p[M]; char s[N]; LL u[M][M];
inline int g(int x,int *o){
	LL cur = 0;
	pre(i, k, 0)cur = (cur * x + o[i]) % P;
	return cur;
}
#define ck(x) ((x) >= P ? (x) - P : (x))
int main() {
	//freopen("INPUT","r",stdin);
	char ch = getchar();
	while(ch == '0' || ch == '1')s[++n] = ch, ch = getchar();
	read(k);
	pw[0] = 1; rp(i, n)pw[i] = ck(pw[i - 1] << 1);
	rep(i, 0, k - 1){
		read(a[i]), c[i][0] = 1;
		rp(j, i)c[i][j] = ck(c[i - 1][j - 1] + c[i - 1][j]);
	}
	f[0][0][0] = 1; int cur = 1;
	rep(i, 0, k){
		rep(j, 0, k)ad(f[0][i + 1][j], f[0][i][j]), ad(f[1][i + 1][j], f[1][i][j]);
		LL now = 1;
		rep(j, 0, k){
			rep(w, j, k)
				ad(f[0][i + 1][w], f[1][i][w - j] * now % P * c[w][j] % P),
				ad(f[1][i + 1][w], f[0][i][w - j] * now % P * c[w][j] % P);
			now = now * cur % P;
		}ad(cur, cur);
	}
	rep(i, 0, k){
		u[i][0] = 1;
		rp(j, k)u[i][j] = u[i][j - 1] * (i + 1) % P;
		u[i][k + 1] = g(i + 1, a) * 500000004LL % P;
		if(i)ad(u[i][k + 1], u[i - 1][k + 1]);
	}
	rep(i, 0, k){
		LL cur = Pow(u[i][i], P - 2);
		rep(j, i, k + 1)u[i][j] = u[i][j] * cur % P;
		rep(j, i + 1, k)
			pre(w, k + 1, i)
				u[j][w] = (u[j][w] - u[j][i] * u[i][w]) % P;
		p[i] = ck(u[i][k + 1] + P);
	}
	pre(i, k, 0){
		rep(j, 0, i - 1)p[j] = (p[j] - u[j][i] * p[i]) % P;
	}
	cur = 0; int ans = 0, bt = 1;
	rp(i, n){
		if(s[i] == '1'){
			if(i + k < n){
				int t = pw[n - i] - 1; 
				LL X = 0, Y = 0, L = cur + t, R = cur - 1;
				pre(j, k, 0)X = (X * L + p[j]) % P, Y = (Y * R + p[j]) % P;
				ad(ans, X), su(ans, Y);
			}
			else{
				rep(j, 0, k){
					int sum = 0; LL now = 1;
					rep(w, 0, j)
						ad(sum, now * c[j][w] % P * f[bt][n - i][j - w] % P), now = now * cur % P;
					ad(ans, a[j] * 1LL * sum % P);
				}
			}
			ad(cur, pw[n - i]), bt ^= 1;
		}
	}printf("%d\n", ans);
	return 0;
}