#include<bits/stdc++.h>
using namespace std;
int read() {
	char c=getchar(); int x=0,f=1;
	while (c<'0' || c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int dp[200005][20];
char s[200005];
int N[200005],used[20];
const int p=1e9+7;
void add(int &x,int y) {
	x+=y;
	if (x>=p) x-=p;
}
int main() {
	scanf("%s", s+1);
	int n=strlen(s+1);
	for (int i=1; i<=n; i++) {
		if (s[i]>='0' && s[i]<='9') N[i]=s[i]-'0';
		else N[i]=s[i]-'A'+10;
	}
	dp[1][1]=N[1]-1;
	int tot=0;
	for (int i=1; i<n; i++) {
		if (!used[N[i]]) {
			++tot;
			used[N[i]]=1;
		}
		for (int j=1; j<=min(i,16); j++) {
			add(dp[i+1][j],1LL*dp[i][j]*j%p);
			if (j<16) add(dp[i+1][j+1],1LL*dp[i][j]*(16-j)%p);
		}
		for (int k=0; k<N[i+1]; k++) {
			if (used[k]) add(dp[i+1][tot],1);
			else add(dp[i+1][tot+1],1);
		}
		add(dp[i+1][1],15);
	}
	if (!used[N[n]]) {
		++tot;
		used[N[n]]=1;
	}
	int k=read();
	int ans=dp[n][k];
	if (tot==k) add(ans,1);
	printf("%d\n", ans);
	return 0;
}
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int main()
{
    int n ,ans = 0;
    scanf("%d",&n);
    vector <int> a(n);
    for(int&i : a){
        scanf("%d",&i);
        ans = (ans + 1LL*i*i%mod)%mod;
    }
    sort(a.begin() ,a.end());
    int bef = a[0];
    for(int i=1; i<n; i++){
        ans = (ans + 1LL*a[i]*bef%mod)%mod;
        bef = (2LL*bef + a[i])%mod;
    }
    printf("%d\n",ans);
}
