#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define infL (1LL<<60)
#define inf (1<<30)
#define inf9 (1000000000)
#define MOD 1000000007//998244353//1000000007
#define EPS 1e-9
#define Gr 9.8
#define PI acos(-1)
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REQ(i,n) for(int (i)=1;(i)<=(int)(n);(i)++)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define readmp(n) for(int i=0,u,v;i<n;i++) {scanf("%d%d",&u,&v); mp[u].push_back(v); mp[v].push_back(u);}
typedef  long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef ll ValType;
template<typename  T> void maxtt(T& t1, T t2) {
    t1=max(t1,t2);
}
template<typename  T> void mintt(T& t1, T t2) {
    t1=min(t1,t2);
}
#define MAX (200135)

bool debug = 0;
int n,m,k;
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
string direc="RDLU";
const ll MOD2 = (ll)MOD * (ll)MOD;
ll ln, lk, lm;
void etp(bool f = 0) {
    puts(f ?"YES" : "NO");
    exit(0);
}
void addmod(int &x, int y, int mod = MOD){
    x+=y; if (x>=mod) x-=mod;
    if(x<0) x+=mod;
    assert(x>=0 && x<mod);
}
void et(int x=-1) {
    printf("%d\n", x); exit(0);
}
ll fastPow(ll x, ll y, int mod=MOD) {
    ll ans = 1;
    while(y>0) {
        if(y&1) ans = (x * ans)%mod;
        x = x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gcd1(ll x, ll y) {
    return y?gcd1(y,x%y):x;
}



char s[MAX];
int gn(char x) {
    if(x>='0' && x<='9') return x-'0';
    else return (x-'A') + 10;
}
int fac[MAX],inv[MAX];
void initfac(int n) {
    fac[0]=inv[0]=1;
    REQ(i,n) {
        fac[i]=(ll)fac[i-1]*i%MOD; inv[i]=fastPow(fac[i], MOD-2);
    }
}
int C(int n, int m) {
    if (n<m) return 0;
    return (ll)fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int S[MAX][17];
void init() {
    S[0][0]=1;
    REQ(i,MAX-5) {
        S[i][0]=0;
        for(int j=1;j<=min(i,16);j++) {
            S[i][j] = ((ll)S[i-1][j-1] + (ll)S[i-1][j] * (j) % MOD)%MOD;
        }
    }
}
void fmain(int tid) {
    scanf("%s%d", s+1, &k);
    n=strlen(s+1);
    initfac(MAX-5); init();
    
    int preM = 0;
    int ans=0;
    for(int i=2;i<=n;i++) {
        int x=n-i;
        if(x+1<k) break;

        int ccc=1;
        int ws=C(16-ccc,k-ccc);
        int pp=0;
        for(int z=k-ccc;z<=k;z++) {
           addmod(pp, (ll)C(ccc, z-(k-ccc)) * S[x][z] % MOD * fac[z] % MOD);
        }
        addmod(ans, (ll)pp*ws%MOD*15%MOD);
    }
    REQ(i,n) {
        int x=n-i;
        //1, b-all 0
        int num=gn(s[i]);
        for(int j=(i==1 ? 1 : 0);j<num;j++) {
            int tmp=preM;
            tmp |= 1<<j;
            int ccc = __builtin_popcount(tmp);
            if (ccc>k) continue;
            int ws=C(16-ccc,k-ccc);
            int pp=0;
            for(int z=k-ccc;z<=k;z++) {
               addmod(pp, (ll)C(ccc, z-(k-ccc)) * S[x][z] % MOD * fac[z] % MOD);
            }
            addmod(ans, (ll)pp*ws%MOD);
        }
        preM |= 1<<num;
    }
    if(__builtin_popcount(preM)==k) addmod(ans, 1);
    printf("%d\n", ans);
}
int main() {
    int t=1;
//    init();
//    scanf("%d", &t);
    REQ(i,t) {
        fmain(i);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1002;
int n,m;
char s[2];
struct node
{
	int s,t,sp;
} r;
queue<node>q;
vector<int>a[N][26];
int ans=1e9,vis[N][N];
//把边看成点
//对于两对边(a,b)  (c,d)
//如果(a,c) 和 (b,c)之间存在边 而且边上的字母相同的话
//那么这两个边变成的点就可以联通
int bfs()
{
	while(!q.empty())
	{
		r=q.front();
		q.pop();
		if(r.sp==ans)
			return ans<<1;
		for(int i=0; i<26; ++i)
			for(int j=0; j<a[r.s][i].size(); ++j)
				for(int k=0; k<a[r.t][i].size(); ++k)
				{
					int ns=a[r.s][i][j];
					int nt=a[r.t][i][k];
					if(ns==r.t||nt==r.s)return r.sp<<1|1;
					if(ns==nt)ans=r.sp+1;
					if(vis[ns][nt])continue;
					vis[ns][nt]=1;
					q.push((node){ns,nt,r.sp+1});
				}
	}
	return -1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int x,y; m; --m)
	{
		scanf("%d%d%s",&x,&y,s);
		a[x][*s-'a'].push_back(y);
		a[y][*s-'a'].push_back(x);
	}
	vis[1][n]=1;
	q.push((node){1,n,0});
	printf("%d",bfs());
}
