#include <bits/stdc++.h>
#include <queue>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int mod = 1e9 + 7;

int binpow(int n, int a){
	int res = 1;
	for (int exp = n; a; a >>= 1, exp = 1LL * exp * exp % mod){
		if (a & 1) res = 1LL * res * exp % mod;
	}
	return res;
}

int inverse(int x){
	return binpow(x, mod - 2);
}

int player;
using Poly = vector<int>;

Poly multiply(const Poly &A, const Poly &B){
	// O(n^2) multiplication
	Poly res(A.size() + B.size() - 1);

	for (int i = 0; i < (int)A.size(); i++){
		for (int j = 0; j < (int)B.size(); j++){
			res[i + j] = (res[i + j] + 1LL * A[i] * B[j]) % mod;
		}
	}

	return res;
}

auto size_comp = [](Poly A, Poly B){ return A.size() > B.size(); };

Poly multiply(const vector<Poly> &V){
	priority_queue<Poly, vector<Poly>, decltype(size_comp)> pq(size_comp);

	for (Poly P: V) pq.push(P);
	while (pq.size() >= 2){
		Poly p1 = pq.top(); pq.pop();
		Poly p2 = pq.top(); pq.pop();
		pq.push(multiply(p1, p2));
	}

	return pq.top();
}

Poly lagrange(const vector<pair<int, int>> &V){
	int n = V.size();

	vector<int> X(n), Y(n);
	for (int i = 0; i < n; i++){
		tie(X[i], Y[i]) = V[i];
	}

	Poly total(n);
	for (int i = 0; i < n; i++){
		vector<Poly> vec; vec.reserve(n - 1);

		int num = Y[i];

		for (int j = 0; j < n; j++){
			if (j == i) continue;
			vec.push_back(Poly{-X[j], 1});
			num = 1LL * num * inverse(X[i] - X[j]) % mod;
		}

		Poly prod = multiply(vec);
		for (int j = 0; j < (int)prod.size(); j++){
			total[j] = (total[j] + 1LL * prod[j] * num) % mod;
		}
	}

	return total;
}

namespace encode {
	string convert(int x){
		if (x < 0) x += mod;
		string repr;
		for (int i = 29; i >= 0; i--){
			repr += ((x >> i) & 1) + '0';
		}
		return repr;
	}

	void solve(){
		int n; cin >> n;

		vector<pair<int, int>> vec(n);
		for (int i = 0; i < n; i++){
			cin >> vec[i].first >> vec[i].second;
		}

		Poly f = lagrange(vec);
		string answer;

		for (int i = 0; i < (int)f.size(); i++){
			answer += convert(f[i]);
		}

		cout << answer.size() << "\n" << answer << "\n";
	}
}

namespace decode {
	int convert(string s){
		int num = 0;
		for (int i = 0; i < 30; i++){
			int digit = (s[i] - '0');
			num = (num << 1) + digit;
		}
		return num;
	}

	int n, q, k;

	void solve(){
		cin >> n >> q >> k;
		string S; cin >> S;

		vector<int> f(n);
		for (int i = 0; i < n; i++){
			f[i] = convert(S.substr(i * 30, 30));
		}

		for (int _ = 0; _ < q; _++){
			int x; cin >> x;

			int P = 1;
			int res = 0;
			for (int j = 0; j < n; j++){
				res = (res + 1LL * P * f[j]) % mod;
				P = 1LL * P * x;
			}

			cout << res << "\n";
		}
	}
}

void main_program(){
	cin >> player;

	if (player == 1) encode::solve();
	else decode::solve();
}