#include <bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
using namespace std;
ll dp[105][100005];
ll t[105];
ll n;
ll totalsum=0;
ll solve(ll pos,ll sum)
{
    if(sum>totalsum/2)
    return INT_MIN;
    if(pos>=n&&sum<=totalsum/2)
    return sum;
    ll &ans=dp[pos][sum];
    if(ans!=-1)
    return ans;
    ans=0;
    ans=max(solve(pos+1,sum),solve(pos+1,sum+t[pos]));
    return ans;
}
int main() {
    fast();
    // ll t;
    // cin>>t;
    // while(t--)			
    // {
         
    // } 
    memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>t[i];
        totalsum+=t[i];
    }
    // cout<<totalsum<<" ";
    cout<<totalsum-solve(0,0);
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxl=2e5+10;
const int mod=1e9+7;
 
int n,k;
int a[maxl];
ll dp[maxl][17][2][2];
char s[maxl];
 
inline ll dfs(int pos,int st,bool up,bool lead)
{
	int cnt=__builtin_popcount(st);
	if(cnt>k) return 0;
	if(pos>n) return cnt==k;
	ll &ret=dp[pos][cnt][up][lead];
	if(ret!=-1)
		return ret;
	ret=0;
	int r=up?a[pos]:15;
	for(int i=0;i<=r;i++)
		ret=(ret+dfs(pos+1,(!i&&!lead)?st:st|(1<<i),up&&(i==r),lead|i))%mod;
	return ret;
}
 
int main()
{
	scanf("%s",s+1);scanf("%d",&k);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	if(s[i]>='A' && s[i]<='Z')
		a[i]=s[i]-'A'+10;
	else
		a[i]=s[i]-'0';
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",dfs(1,0,1,0));
	return 0;
}