#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>
#include<map>
#include<cassert>

using namespace std;

#define ll long long
#define reps(i, a, b) for(int i = a; i < b; i++)
#define rreps(i, a, b) for(int i = a-1; i >= b; i--)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) rreps(i, n, 0)
#define P pair<int, int>
#define vec vector<int>
#define mat vector<vec>

const ll mod = 1000000007;
const int INF = 1001001001;

struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};
istream& operator>>(istream& is, const mint& a){ return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a){ return os << a.x; }

set<char> s;
map<char, int> mp, mp_inv;

int C(char c){
    int num = mp[c];
    int res = 0;
    rep(i, num){
        if(s.find(mp_inv[i]) == s.end())res++;
    }
    return res;
}

int main(){
    string n;
    int k;
    cin >> n >> k;
    int keta = 0;
    for (int i = 0; n[i] != 0; i++) keta++;

    rep(i, 10) {
        mp[(char)('0'+i)] = i;
        mp_inv[i] = '0' + i;
    }
    rep(i, 6) {
        mp[(char)('A'+i)] = i + 10;
        mp_inv[i+10] = 'A' + i;
    }

    vector<vector<vector<mint> > > dp(keta+1, vector<vector<mint> >(k+1, vector<mint>(2)));
    dp[0][0][0] = 1;


    rep(i, keta){
        dp[i+1][0][0] = 0;
        dp[i+1][0][1] = 1;
        rep(j, k){
            if(s.find(n[i]) == s.end()) dp[i+1][j+1][0] = dp[i][j][0];
            else dp[i+1][j+1][0] = dp[i][j+1][0];
            
            int c = C(n[i]);

            if(j != 0){
                if(i == 0) dp[i+1][j+1][1] = dp[i][j][0] * (c-1) + dp[i][j+1][0] * (mp[n[i]]-c) + dp[i][j][1]*(16-j) + dp[i][j+1][1] * (j+1);   
                else dp[i+1][j+1][1] = dp[i][j][0] * c + dp[i][j+1][0] * (mp[n[i]]-c) + dp[i][j][1]*(16-j) + dp[i][j+1][1] * (j+1); 
            }else{
                if(i == 0) dp[i+1][j+1][1] = dp[i][j][0] * (c-1) + dp[i][j+1][0] * (mp[n[i]]-c) + dp[i][j][1]*(16-j-1) + dp[i][j+1][1] * (j+1);   
                else dp[i+1][j+1][1] = dp[i][j][0] * c + dp[i][j+1][0] * (mp[n[i]]-c) + dp[i][j][1]*(16-j-1) + dp[i][j+1][1] * (j+1); 
            }
  
        }
        s.insert(n[i]);
    }
    // rep(j, k+1){
    //     rep(i, keta+1){
    //         cout << dp[i][j][0] << " ";
    //     }cout << endl;
    // }cout << endl;

    // rep(j, k+1){
    //     rep(i, keta+1){
    //         cout << dp[i][j][1] << " ";
    //     }cout << endl;
    // }
    mint ans;
    ans = dp[keta][k][0] + dp[keta][k][1];
    cout << ans << endl;
}
#include <bits/stdc++.h>
//#include <atcoder/all>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
template <class T>
inline bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;
//using namespace atcoder;

template<int mod>
struct Modint{
    int x;
    Modint():x(0){}
    Modint(int64_t y):x((y%mod+mod)%mod){}

    Modint &operator+=(const Modint &p){
			if((x+=p.x)>=mod)
				x -= mod;
			return *this;
		}

		Modint &operator-=(const Modint &p){
			if((x+=mod-p.x)>=mod)
				x -= mod;
			return *this;
		}

		Modint &operator*=(const Modint &p){
			x = (1LL * x * p.x) % mod;
			return *this;
		}

		Modint &operator/=(const Modint &p){
			*this *= p.inverse();
			return *this;
		}

		Modint operator-() const { return Modint(-x); }
		Modint operator+(const Modint &p) const{
			return Modint(*this) += p;
		}
		Modint operator-(const Modint &p) const{
			return Modint(*this) -= p;
		}
		Modint operator*(const Modint &p) const{
			return Modint(*this) *= p;
		}
		Modint operator/(const Modint &p) const{
			return Modint(*this) /= p;
		}

		bool operator==(const Modint &p) const { return x == p.x; }
		bool operator!=(const Modint &p) const{return x != p.x;}

		Modint inverse() const{//非再帰拡張ユークリッド
			int a = x, b = mod, u = 1, v = 0;
			while(b>0){
				int t = a / b;
				swap(a -= t * b, b);
				swap(u -= t * v, v);
			}
			return Modint(u);
		}

		Modint pow(int64_t n) const{//繰り返し二乗法
			Modint ret(1), mul(x);
			while(n>0){
				if(n&1)
					ret *= mul;
				mul *= mul;
				n >>= 1;
			}
			return ret;
		}

		friend ostream &operator<<(ostream &os,const Modint &p){
			return os << p.x;
		}

		friend istream &operator>>(istream &is, Modint &p){
			int64_t t;
			is >> t;
			p=Modint<mod>(t);
			return is;
		}
};

using modint = Modint<mod>;

void solve(){
	ll t;
	cin>>t;
	while(t--){
		ll n,a,b;
		cin>>n>>a>>b;
		if(n<a+b){
			cout<<0<<"\n";
			continue;
		}
		auto f=[&](modint x)->modint{
			return x*x;
		};
		modint ans=f(n-a+1)*f(n-b+1);
		modint x=min(a,b)-1;
		ans-=f(x)*f(x+3+2*n-2*(a+b))/4*4;//縦も横も完全にはかぶらない
		modint s=max(a,b);
		ans-=(s-x)*x*(-s+n+1)*(x+3+2*n-2*(a+b))*2;
		ans-=f(s-x)*f(-s+n+1);//縦も横も完全にかぶる
		cout<<ans<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}
