#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;
#include<iostream>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int mod = 1e9 + 7;
int dp[2][100][100];
int AB[200], *A = AB, *B = AB + 100;
constexpr ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, M, K;
	cin >> N >> M >> K;
	rep(i, N) {
		cin >> A[i];
	}
	auto mae = dp[0], ato = dp[1];
	int are = modpow(2 * M, mod - 2);

	rep(i, M) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		if (x < y) swap(x, y);
		mae[x][x]--;
		mae[x][y]++;
		mae[y][y]--;
	}
	rep(x, N) rep(y, x + 1) {
		mae[x][y] = (ll(mae[x][y] + mod) * are + (x == y)) % mod;
		mae[y][x] = mae[x][y];
	}

	const ll ma = (1ll << 32) - 1;

	rep(i, 30) {
		if (K >> i & 1) {
			rep(i, N) {
				ll t1 = 0, t2 = 0;
				rep(j, N) {
					auto tmp = (ll)mae[i][j] * A[j];
					t1 += tmp >> 32;
					t2 += tmp & ma;
				}
				B[i] = ((t1 % mod << 32) + t2) % mod;
			}
			swap(A, B);
		}
		if (!K | i >= 31 - __builtin_clz(K)) break;
		rep(x, N) rep(y, x + 1) {
			auto tmp1 = mae[x];
			auto tmp2 = mae[y];
			ll t1 = 0, t2 = 0;
			rep(z, N) {
				auto tmp = *tmp1++ * (ll)*tmp2++;
				t1 += tmp >> 32;
				t2 += tmp & ma;
			}
			ato[y][x] = (ato[x][y] = ((t1 % mod << 32) + t2) % mod);
		}
		swap(mae, ato);
	}

	rep(i, N) co(A[i]);


	Would you please return 0;
}
// Author : heyuhhh
// Created Time : 2021/03/07 19:18:55
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5, M = 17, MOD = 1e9 + 7;

inline int add(int x, int y) {
    return x + y >= MOD ? x + y - MOD : x + y;
}
inline int dec(int x, int y) {
    return x - y < 0 ? x - y + MOD : x - y;
}
inline int mul(int x, int y) {
    return 1ll * x * y % MOD;
}

string s;
int n, k;
int dp[N][M];
int cnt[M];

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

void run() {
    cin >> s >> k;
    n = s.length();
    int pre = 0;
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= min(i, k); ++j) {
            if (j == 0) {
                if (i > 0) {
                    dp[i + 1][1] = add(dp[i + 1][1], 15);
                    dp[i + 1][0] = add(dp[i + 1][0], 1);
                }
            } else {
                dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(16 - j, dp[i][j]));
                dp[i + 1][j] = add(dp[i + 1][j], mul(j, dp[i][j]));
            }
        }
        for (int t = (pre == 0); t < trans(s[i]); ++t) {
            if (++cnt[t] == 1) dp[i + 1][pre + 1] = add(dp[i + 1][pre + 1], 1);
            else dp[i + 1][pre] = add(dp[i + 1][pre], 1);
            --cnt[t];
        }
        if (++cnt[trans(s[i])] == 1) ++pre;
    }
    int ans = dp[n][k] + (pre == k);
    cout << ans << '\n';
}
int main() {
#ifdef Local
    freopen("input.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}