#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin( ), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
}
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
}
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
}
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
    }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
}
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
         return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<MOD>;

mint dp[202020][20];
int main(){
    string N; int K; cin >> N >> K;
    int mask = 0; //Nに使用された数字のマスクビット

    rep(i, N.size()){
        char c = N[i]; int y;
        if(c>='A' and c<='F')y=10+c-'A';
        else y=(c-'0');

        //直前まで(1つ以上の)0,初めて0以外の数字が出る
        if(i>0)dp[i+1][1] += 15;
        //直前までNと同一、初めてN未満になる
        rep(j, y){
            if(i==0 and j==0)continue; //初桁のみ0は選べない
            int x = __builtin_popcount(mask | 1<<j); //数字jを採用したときの種類数
            dp[i+1][x] += 1;
        }
        //その他
        rep(j, 17){
            dp[i+1][j] += dp[i][j] * j;
            dp[i+1][j+1] += dp[i][j] * (16 - j);
        }
        mask |= (1<<y);
    }

    mint res = dp[N.size()][K];
    if(__builtin_popcount(mask)  == K)res += 1;
    cout << res << ln;
}

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <functional>
#include <cassert>
#include <stack>
#include <numeric>
#include <iomanip>
#include <limits>
#include <random>
#include <unordered_map>

typedef int64_t ll;
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> Pdd;

#define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++)
#define all(_l) _l.begin(), _l.end()
#define rall(_l) _l.rbegin(), _l.rend()
#define MM << " " <<

template<typename _T>
using MaxHeap = std::priority_queue<_T>;
template<typename _T>
using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>;

template<typename _T>
inline bool chmax(_T &_l, const _T _b) {
    if (_l < _b) {
        _l = _b;
        return true;
    }
    return false;
}
template<typename _T>
inline bool chmin(_T &_l, const _T _b) {
    if (_l > _b) {
        _l = _b;
        return true;
    }
    return false;
}

template<typename _T>
void vdeb(const std::vector<_T> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        if (i == bb.size() - 1) std::cout << bb[i];
        else std::cout << bb[i] << ' ';
    }
    std::cout << '\n';
}
template<typename _T>
void vdeb(const std::vector<std::vector<_T>> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        std::cout << i << ' ';
        vdeb(bb[i]);
    }
    std::cout << '\n';
}

using namespace std;

int main() {
    int n; cin >> n;
    vector<Pll> da(n);
    ll lower = LLONG_MIN/2, upper = LLONG_MAX/2, offset = 0, up = LLONG_MAX/2, lo = LLONG_MIN/2;
    rip(i,n,0) {
        cin >> da[i].first >> da[i].second;
        if(da[i].second == 1) {
            lo += da[i].first;
            up += da[i].first;
            offset += da[i].first;
        }
        else if(da[i].second == 2) {
            chmax(up, da[i].first);
            chmax(lo, da[i].first);
            chmax(lower, da[i].first-offset);
        }
        else if(da[i].second == 3) {
            chmin(up, da[i].first);
            chmin(lo, da[i].first);
            chmin(upper, da[i].first-offset);
        }
    }
    
    int q; cin >> q;
    vector<ll> ans(q);
    rip(i,q,0) {
        int x; cin >> x;
        if(upper <= x) ans[i] = up;
        else if(x <= lower) ans[i] = lo;
        else ans[i] = x+offset;
    }
    for(auto &&i : ans) cout << i << endl;
}