#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;
const int MOD = 1e9+7;
const int N = 1e2+10;
const int K = 3e3+10;
int n;
int x[N], y[N];
int func[N];
int tempfunc[N];
int zerofunc[N];
int strlength;
string strfunc;
int q;
int querries[N];

int add( int a, int b ) {return (a+b >= MOD) ? a+b-MOD : a+b;}

int sub( int a, int b ) {return add(a, MOD-b);}

int mul( int a, int b ) {return (ll) a * b % MOD;}

int bin_exp( int a, int k ) {
	int out = 1;
	while(k) {
		if(k&1) {
			out = mul(out, a);
		}
		a = mul(a, a);
		k/=2;
	}
	return out;
}

int divide( int a, int b ) {
	return mul(a, bin_exp(b, MOD-2));
}

string tostring( int a ) {
	string out = "";
	for(int i = 29; i >= 0; i--) {
		if((1<<i) & a) out += '1';
		else out += '0';
	}
	return out;
}

void upis1( void ) {
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	return;
}

void solve1( void ) {
	zerofunc[0] = 1;
	for(int i = 0; i < n; i++) {
		for(int j = i; j >= 0; j--) {
			zerofunc[j+1] = add(zerofunc[j+1], zerofunc[j]);
			zerofunc[j] = mul(zerofunc[j], x[i]);
		}
	}
	int cury;
	int tempx;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n+1; j++) {
			tempfunc[j] = zerofunc[j];
		}
		for(int j = 0; j < n; j++) {
			tempfunc[j] = divide(tempfunc[j], x[i]);
			tempfunc[j+1] = sub(tempfunc[j+1], tempfunc[j]);
		}
		cury = 0;
		tempx = 1;
		for(int j = 0; j < n; j++) {
			if((j&1) == ((n-1)&1)) cury = add(cury, mul(tempx, tempfunc[j]));
			else cury = sub(cury, mul(tempx, tempfunc[j]));
			tempx = mul(tempx, x[i]);
		}
		for(int j = 0; j < n; j++) {
			func[j] = add(divide(mul(tempfunc[j], y[i]), cury), func[j]);
		}
	}
	cout << n*30 << "\n";
	for(int i = 0; i < n; i++) cout << tostring(func[i]);
	return;
}

void upis2( void ) {
	cin >> n >> q >> strlength;
	cin >> strfunc;
	for(int i = 0; i < q; i++) cin >> querries[i];
	return;
}

void solve2( void ) {
	for(int i = 0; i < n; i++) {
		for(int j = i*30; j < (i+1)*30; j++) {
			func[i] *= 2;
			func[i] += (int) (strfunc[j] == '1');
		}
	}
	int tempx;
	int tempy;
	for(int i = 0; i < q; i++) {
		tempy = 0;
		tempx = 1;
		for(int j = 0; j < n; j++) {
			if((j&1) == ((n-1)&1)) tempy = add(tempy, mul(func[j], tempx));
			else tempy = sub(tempy, mul(func[j], tempx));
			tempx = mul(tempx, querries[i]);
		}
		cout << tempy << "\n";
	}
	return;
}

int main( void ) {
	
	FIO;
	int t;
	cin >> t;
	if(t==1) {
		upis1();
		solve1();
	}
	else {
		upis2();
		solve2();
	}
	
	return 0;
}