#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define F first
#define S second
#define pss pair<string,string>
#define pcc pair<char,char>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define piii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define vs vector<string>
#define vl vector<ll>
#define vs vector<string>
#define vll vector<pll>
#define vss vector<pss>
#define vcc vector<pcc>
#define MP make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define Very_fast std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int N = 1e5+5;
int mod=10;
const int INF=0x3f3f3f3f;
inline ll gcd(ll a,ll b){if(b==0)return a;else return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll lowbit(ll x){return (x&-x);}
inline ll kissme(ll x,ll y)
{
	ll res=1;
	if(x==0)return 1;
	if(x==1)return y;
	res=kissme(x/2,y);
	res=res*res%mod;
	if(x%2==1)res=res*y%mod;
	return res;
}
ll a,b,c;vi v[20];
void init()
{
	v[0].pb(0);
	v[1].pb(1);
	v[2].pb(2);
	v[2].pb(4);
	v[2].pb(8);
	v[2].pb(6);
	v[3].pb(3);
	v[3].pb(9);
	v[3].pb(7);
	v[3].pb(1);
	v[4].pb(4);
	v[4].pb(6);
	v[5].pb(5);
	v[6].pb(6);
	v[7].pb(7);
	v[7].pb(9);
	v[7].pb(3);
	v[7].pb(1);
	v[8].pb(8);
	v[8].pb(4);
	v[8].pb(2);
	v[8].pb(6);
	v[9].pb(9);
	v[9].pb(1);
}
signed main()
{
	Very_fast;
	init();
	cin>>a>>b>>c;
	mod=v[a%10].size();
	cout<<v[a%10][(kissme(c,b)-1+mod)%mod];
	return 0;
}
#include <iostream>
#include <cstring>

using namespace std;
using ll = long long;
const int N = 200005, P = 1e9 + 7;

char s[N];
int n, k;
ll f[N][17];

int to_num(char c)
{
    if ('0' <= c && c <= '9')
        return c ^ '0';
    return 10 + c - 'A';
}

void init()
{
    f[0][k] = 1;
    for (int i = 1; i < n; ++i)
        for (int j = k; ~j; --j)
            f[i][j] = (j * f[i - 1][j] + (16 - j) * f[i - 1][j + 1]) % P;
}

ll dp(char s[])
{
    ll res = 0;
    int i = 0, cnt = 0;
    bool st[16];
    memset(st, 0, sizeof st);
    for (int j = 1; j < n; ++j)
        res = (res + f[j][0] - f[j - 1][1]) % P;
    while (i < n)
    {
        int c = to_num(s[i]), l = n - i - 1;
        for (int j = 0; j < c; ++j)
            if (st[j])
                res = (res + f[l][cnt]) % P;
            else if (i || j)
                res = (res + f[l][cnt + 1] % P);
        if (!st[c])
            ++cnt, st[c] = true;
        if (++i == n && k == cnt)
            ++res;
    }
    return res;
}

int main()
{
    scanf("%s%d", s, &k);
    n = strlen(s);
    init();
    cout << dp(s) << endl;
}
