#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MOD = 1'000'000'000 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int k;
    cin >> k;

    auto combination = [&](int n, int m) {
        if (m == 0 || n == 0)
            return 1LL;
        ll res = 1;
        ll div = 1;
        for (int i = n; i > n - m; --i)
            res *= i;
        for (int i = m; i > 1; --i)
            div *= i;
        return res / div;
    };

    auto modpow = [&](ll base, ll pow) {
        ll res = 1;
        while (pow) {
            if (pow & 1)
                res = res * base % MOD;
            base = base * base % MOD;
            pow >>= 1;
        }
        return res;
    };

    auto less = [&](int len, int unique) {
        int rem = k - unique;
        if (unique > k || len < rem)
            return 0LL;
        if (len == 0)
            return 1LL;
        if (rem == 0) {
            return modpow(k, len);
        }
        ll choice = combination(16 - unique, rem);
        ll ans = 0;
        for (int i = 0; i <= rem; ++i) {
            ll sign = i % 2 == 0 ? 1LL : -1LL;
            ans = (ans + sign * (combination(rem, i) * modpow(k - i, len) % MOD) + MOD) % MOD;
        }
        return ans * choice % MOD;
    };

    auto translate = [&](char c) {
        if (isdigit(c))
            return c - '0';
        return 10 + (c - 'A');
    };

    int unique = 0;
    vector<bool> digit(16);
    ll ans = 0;
    for (int i = 0; i < s.length(); ++i) {
        int decimal = translate(s[i]);
        for (int j = 0; j < decimal; ++j) {
            if (i == 0 && j == 0)
                continue;
            ll tmp = less(s.length() - i - 1, unique + (digit[j] == 0));
            ans = (ans + tmp) % MOD;
        }
        if (!digit[decimal])
            ++unique;
        digit[decimal] = true;
        if (unique > k)
            break;
    }

    for (int i = 0; i < s.length() - 1; ++i) {
        ll tmp = 15LL * less(i, 1);
        ans = (ans + tmp) % MOD;
    }
    
    if (unique == k)
        ans = (ans + 1) % MOD;

    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
#include <map>
#include <iostream>

using namespace std;
typedef long long ll;
typedef long double ld;
#define BIG 2005

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> dp(BIG, vector<int>(BIG, -1));
    vector<string> ma(BIG);
    for(int h=0;h<H;h++){
        cin >> ma[h];
    }
    vector<vector<int>> alpha(27, vector<int>());  //a-zの場所を保存する
    vector<bool> did(27, false);
    int sh, sw;
    for(int h=0;h<H;h++){
        for(int w=0;w<W;w++){
            if(ma[h][w]=='S'){
                sh = h;
                sw = w;
            }
            int sn = ma[h][w] - 'a';
            if(0<=sn && sn <= 26){
                alpha[sn].push_back(h*BIG+w);
            }
        }
    }
    dp[sh][sw] = 0;
    set<int> search;
    search.insert(sh*BIG+sw);
    int count = 0;
    while(!search.empty()){
        count++;
        // searchから辿り着けるところのステップを求める
        set<int> next;
        for(auto hw: search){
            int ch = hw / BIG;
            int cw = hw % BIG;
            // ワープできるならする。
            int cn = ma[ch][cw] - 'a';
            if(0<=cn && cn <=26 && !did[cn]){
                // alphabet, ワープしていない
                did[cn] = true;
                // ワープ先で探索していない箇所のステップを決定して、nextに加える
                for(auto wn: alpha[cn]){
                    int wh = wn / BIG;
                    int ww = wn % BIG;
                    if(dp[wh][ww]==-1){
                        dp[wh][ww] = count;
                        next.insert(wn);
                    }
                }
            }
            // 周りの四箇所に移動できれば、移動さきを調べる
            // 移動さきが探索できていなければ、ステップを決定して,nextに加える
            // -1, 0
            if(ch-1>=0){
                if(dp[ch-1][cw]==-1 && ma[ch-1][cw]!='#'){
                    dp[ch-1][cw] = count;
                    next.insert((ch-1)*BIG+cw);
                }
            }
            // 1, 0
            if(ch+1<H){
                if(dp[ch+1][cw]==-1 && ma[ch+1][cw]!='#'){
                    dp[ch+1][cw] = count;
                    next.insert((ch+1)*BIG+cw);
                }
            }
            // 0, 1
            if(cw+1<W){
                if(dp[ch][cw+1]==-1 && ma[ch][cw+1]!='#'){
                    dp[ch][cw+1] = count;
                    next.insert(ch*BIG+cw+1);
                }
            }
            // 0, -1
            if(cw-1>=0){
                if(dp[ch][cw-1]==-1 && ma[ch][cw-1]!='#'){
                    dp[ch][cw-1] = count;
                    next.insert(ch*BIG+cw-1);
                }
            }
        }
        search = next;
    }
    // goal
    int gh, gw;
    for(int h=0;h<H;h++){
        for(int w=0;w<W;w++){
            if(ma[h][w]=='G'){
                gh = h;
                gw = w;
            }
        }
    }
    printf("%d\n", dp[gh][gw]);
    return 0;
}