PLAN

#define task "PLAN"

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e1 + 5;
constexpr ll mod = 1e9;
int n, a[N], b[N], m;
int dp[10][11][452][452];
string A, B;

void Read()
{
    cin >> n >> A >> B;
    for (int i = 0; i < n; ++i)
        cin >> a[i] >> b[i];
}

inline void Add(int &x, int y)
{
    x += y;
    if (x >= mod)
        x -= mod;
}

void Solve()
{
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());

    A.resize(max(A.size(), B.size()), '0');
    B.resize(A.size(), '0');

    m = A.size();

    dp[0][0][0][0] = 1;

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
            for (int digit = 0; digit < 10; ++digit)
                for (int t = 0; t <= 450 - digit * a[j]; ++t)
                    for (int h = 0; h <= 450 - digit * b[j]; ++h)
                        Add(dp[i][j + 1][t + a[j] * digit][h + b[j] * digit], dp[i][j][t][h]);
        if (i < m - 1)
            for (int t = 0; t <= 450; ++t)
                for (int h = 0; h <= 450; ++h)
                    if (t % 10 == A[i] - '0' && h % 10 == B[i] - '0')
                        Add(dp[i + 1][0][t / 10][h / 10], dp[i][n][t][h]);
    }

    cout << dp[m - 1][n][A[m - 1] - '0'][B[m - 1] - '0'];
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}