#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yes(ans) if(ans)printf("yes\n");else printf("no\n")
#define Yes(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YES(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector1d(type,name,...) vector<type>name(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
const int MOD2=998244353;
const int INF=1<<30;
const ll INF2=(ll)1<<60;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T,class L>void scan(pair<T, L>& p){scan(p.first);scan(p.second);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T,class L>void print(const pair<T, L>& p){print(p.first);putchar(' ');print(p.second);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll updivide(ll a,ll b){if(a%b==0) return a/b;else return (a/b)+1;}
template<class T> void chmax(T &a,const T b){if(b>a)a=b;}
template<class T> void chmin(T &a,const T b){if(b<a)a=b;}

int main(){
    INT(n,m);
    vector<ll> h(n),w(m);
    in(h,w);
    vector<ll> oddsum(1,0),evensum(1,0),odd(1,0),even(1,0);
    sort(all(h));
    for(int i=0;i<n;i++){
        if(i%2==0){
            odd.push_back(h[i]);
            oddsum.push_back(oddsum[oddsum.size()-1]+h[i]);
        }else{
            even.push_back(h[i]);
            evensum.push_back(evensum[evensum.size()-1]+h[i]);
        }
    }
    int insert_index,oindex,eindex;
    ll fsum,bsum,ans=INF2;
    for(int i=0;i<m;i++){
        insert_index=(int)(upper_bound(all(h),w[i])-h.begin());
        oindex=(int)(upper_bound(all(odd),w[i])-odd.begin())-1;
        eindex=(int)(upper_bound(all(even),w[i])-even.begin())-1;
        fsum=oddsum[oindex];
        bsum=evensum[eindex];
        fsum+=evensum[evensum.size()-1]-evensum[eindex];
        bsum+=oddsum[oddsum.size()-1]-oddsum[oindex];
        if(insert_index%2==1){
            bsum+=w[i];
        }else{
            fsum+=w[i];
        }
        chmin(ans,bsum-fsum);
    }
    out(ans);
}
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 2e5 + 100;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353;

bool used[MAXN];
string s;
ll fans, k, fact[MAXN], inv[MAXN], cval = 0;

inline ll poww(ll a, ll b, ll m = MOD) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}

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

inline ll C(int r, int n) {
	if (r > n || r < 0) return 0;
	return fact[n] * inv[r] % MOD * inv[n - r] % MOD;
}
inline int Check() {
	memset(used, false, sizeof used);
	for (char c : s) used[F(c)] = true;
	int ans = 0;
	for (int i = 0; i < 16; i++) if (used[i]) ans++;
	return ans;
}

inline ll solve(ll k) {
	memset(used, false, sizeof used);
	ll n = s.size(), ans = 0;
	for (int d = 1; d < n; d++) ans += 15 * C(k - 1, 15) % MOD * poww(k, d - 1, MOD) % MOD;

	ans += (F(s.front()) - 1) * C(k - 1, 15) % MOD * poww(k, n - 1, MOD) % MOD;
	ans %= MOD;
	used[F(s.front())] = true;
	for (int i = 1; i < n; i++) {
		char c = s[i];
		ll P2 = 0, P = 0;
		for (int j = 0; j < 16; j++) {
			if (used[j]) {
				P++;
				if (j < F(c)) P2++;
			}
		}

		ans += P2 * C(k - P, 16 - P) % MOD * poww(k, n - i - 1) % MOD;
		ans += (F(c) - P2) * C(k - P - 1, 16 - P - 1) % MOD * poww(k, n - i - 1) % MOD;
		ans %= MOD;
		used[F(c)] = true;
	}

	ans += C(k - cval, 16 - cval);
	return ans % MOD;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fact[0] = inv[0] = 1;
	for (int i = 1; i <= 100; i++) fact[i] = i * fact[i - 1] % MOD, inv[i] = poww(fact[i], MOD - 2, MOD);
	cin >> s >> k;
	
	
	cval = Check();
	for (int i = 1; i <= k; i++) {
		ll tans = solve(i) * C(k - i, 16 - i) % MOD;
		if ((k - i) & 1) tans = -tans;
		fans += tans;
		fans += 2 * MOD;
		fans %= MOD;
	}

	cout << fans << endl;
	return 0;
}
