#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
using matrix = vector<vector<ll>>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
template<class in_chmax> void chmax(in_chmax &x, in_chmax y) {x = max(x,y);}
template<class in_chmin> void chmin(in_chmin &x, in_chmin y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll maxN = 110;

ll powmodp(ll x, ll n) {
    if (n==0) return 1;
    if (n%2) return x * powmodp(x,n-1) % mod;
    ll res = powmodp(x,n/2);
    return res * res % mod;
}

ll inv(ll x) {return powmodp(x,mod-2);}

matrix E(ll n) {
    matrix res(n,vector<ll>(n));
    rep(i,n) res[i][i] = 1;
    return res;
}

void addmodp(ll &x, ll y) {x = (x + y) % mod;}

matrix prodmatrix(matrix x, matrix y) {
    ll H = x.size(), W = y[0].size(), sz = y.size();
    matrix res(H,vector<ll>(W));
    rep(i,H) rep(j,W) rep(k,sz) {
        addmodp(res[i][j], x[i][k] * y[k][j] % mod);
    }
    return res;
}
vector<ll> prodmatrix(matrix A, vector<ll> x) {
    matrix X(x.size(),vector<ll>(1));//         |y1|   |A11    |   |x1|
    rep(i,x.size()) X[i][0] = x[i];  //         |y2| = |  A22  | * |x2|
    matrix Y = prodmatrix(A,X);      //         |y3|   |    A33|   |x3|
    vector<ll> y(Y.size());
    rep(i,Y.size()) y[i] = Y[i][0];
    return y;
}
vector<ll> prodmatrix(vector<ll> x, matrix A) {
    matrix X(1,vector<ll>(x.size()));//                               |A11    |
    rep(i,x.size()) X[0][i] = x[i];  // |y1, y2, y3| = |x1, x2, x3| * |  A22  |
    matrix Y = prodmatrix(X,A);      //                               |    A33|
    vector<ll> y(Y[0].size());
    rep(i,Y[0].size()) y[i] = Y[0][i];
    return y;
}

matrix powmatrix(matrix x, ll n) {
    if (n==0) return E(x.size());
    if (n%2) return prodmatrix(x,powmatrix(x,n-1));
    matrix res = powmatrix(x,n/2);
    return prodmatrix(res,res);
}

ll N, M, K;
vector<ll> A(maxN);
matrix mat(maxN,vector<ll>(maxN));
vector<ll> G[maxN];

int main() {
    cin >> N >> M >> K;
    rep(i,N) cin >> A[i];
    rep(i,M) {
        ll x, y; cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    rep(now,N) {
        ll n = G[now].size();
        ll p = n * inv(M) % mod, q = (1-p+mod) % mod;
        mat[now][now] = ((p * inv(2) % mod) + q) % mod;
        for (ll to : G[now]) {
            mat[now][to] = inv(M) * inv(2) % mod;
        }
    }
    vector<ll> res = prodmatrix(A,powmatrix(mat,K));
    rep(i,N) cout << res[i] << endl;
}
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string n;
    int k;
    cin >> n >> k;
    int sz=n.size();
    n="$"+n;
    const ll mod=1000000007;
    auto add=[&](ll &a,ll b){a=(a+b)%mod;};
    auto digit=[&](char c)->int
    {
        if('0'<=c&&c<='9') return (c-'0');
        else return (10+c-'A');
    };
    vector<ll> dp(17,0);
    vector<bool> c(16,0);
    int cnt=0;
    for(int i=0;i<sz;i++)
    {
        if(i>0)
        {
            if(c[digit(n[i])]==0)
            {
                c[digit(n[i])]=1;
                cnt++;
            }
        }
        vector<ll> ndp(17,0);
        for(int j=0;j<=16;j++)
        {
            if(j>0) add(ndp[j],dp[j]*j);
            if(j<16) add(ndp[j+1],dp[j]*(16-j));
        }
        if(i>0) add(ndp[1],15);
        for(int j=(i==0);j<digit(n[i+1]);j++)
        {
            if(c[j]==1) add(ndp[cnt],1);
            else add(ndp[cnt+1],1);
        }
        dp=ndp;
    }
    add(dp[cnt+(c[digit(n[sz])]==0)],1);
    cout << dp[k] << "\n";
    return 0;
}
