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

constexpr int N = 105, MOD = 1e9 + 7;

namespace Alice
{
    int n;

    int a[N][N];

    int inverse(int x)
    {
        int y = 1, c = MOD - 2;
        while(c)
        {
            if(c & 1)y = 1ll * y * x % MOD;
            x = 1ll * x * x % MOD, c >>= 1;
        }
        return y;
    }

    void work()
    {
        for(int i = 0; i < n; i ++)
        {
            int t = i;
            while(t <= n && a[t][i] == 0) t ++;
            swap(a[i], a[t]);

            int inv = inverse(a[i][i]);
            for(int j = i; j <= n; j ++)
                a[i][j] = 1ll * a[i][j] * inv % MOD;
            
            for(int j = i + 1; j < n; j ++)
            {
                if(a[j][i] == 0)continue;
                for(int k = n; k >= i; k --)
                    a[j][k] = (a[j][k] - 1ll * a[i][k] * a[j][i] % MOD + MOD) % MOD;
            }
        }

        for(int i = n - 1; i >= 0; i --)
            for(int j = i - 1; j >= 0; j --)
                a[j][n] = (a[j][n] - 1ll * a[j][i] * a[i][n] % MOD + MOD) % MOD;
    }

    void solve()
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i ++)
        {
            int x, y;
            scanf("%d%d", &x, &y);

            int w = 1;
            for(int j = 0; j < n; j ++)
            {
                a[i][j] = w;
                w = 1ll * w * x % MOD;
            }
            a[i][n] = y;
        }

        work();

        printf("%d\n", n * 30);
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < 30; j ++)
                printf("%d", a[i][n] >> j & 1);
        }
    }
}

namespace Bob
{
    int n;

    char str[N * 30];
    int a[N];

    int work(int x)
    {
        int w = 1, y = 0;
        for(int i = 0; i < n; i ++)
        {
            y = (y + 1ll * a[i] * w % MOD) % MOD;
            w = 1ll * w * x % MOD;
        }
        return y;
    }

    void solve()
    {
        int m, q;
        scanf("%d%d%d", &n, &q, &m);
        scanf("%s", str);
        n /= 30;

        for(int i = n - 1; i >= 0; i --)
        {
            int val = 0;
            for(int j = 29; j >= 0; j --)
                val = val << 1 | (str[i * 30 + j] - '0');
            a[i] = val;
        }

        while(q --)
        {
            int x;
            scanf("%d", &x);

            printf("%d\n", work(x));
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);

    if(T==1)Alice :: solve();
    else Bob :: solve();

    return 0;
}