#include<bits/stdc++.h>
using namespace std;

#define int         long long
#define ull         unsigned long long
#define ll          long long
#define M           998244353
#define pb          push_back
#define p_q         priority_queue
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mp          make_pair
#define lb          lower_bound
#define ub          upper_bound
#define F           first
#define S           second
#define rep(i, begin, end) for (int i=begin;i<end;i++)
#define repd(i, begin, end) for (int i=end-1;i>=begin;i--)
#define ini(a,n,b)  for(ll int i=0;i<n;i++) a[i]=0;
#define cset(a)     __builtin_popcountll(a)
#define hell        1000000007
#define re          resize
const int INF=1e18;
const int N=1e2+5;


int powm(int a,int b)
{
  int res=1;
  while(b)
  {
    if(b&1) 
    res=(res*a)%M;
      a=(a*a)%M;
      b>>=1;
  }
 
  return res;
}

int pow(int a,int b)
{
  int res=1;
  while(b)
  {
    if(b&1) 
    res=(res*a);
      a=(a*a);
      b>>=1;
  }
 
  return res;
}

vi a[N],vis(N,0),len(N,0);
set<pair<int,int> > s;

void dfs(int node,int par)
{
  vis[node]=1;
  for(auto j:a[node])
  {
    if(!vis[j])
    {
       len[j]=len[node]+1;
       s.insert({node,j});
       dfs(j,node);
    }
    else if(j!=par&&len[j]<len[node])
    {
       s.insert({node,j});
    }
  } 
}
signed main(void)
{ios
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);freopen("answer.txt", "w", stdout);
    #endif

    
    int n,m;
    cin>>n>>m;
    vi u(m),v(m);
    rep(i,0,m)
    {
       cin>>u[i]>>v[i];
    }

    vi c(n+1);
    rep(i,1,n+1) cin>>c[i];
    vi dir(m,0);
    rep(i,0,m)
    {
       if(c[u[i]]>c[v[i]])
       {
         dir[i]=1;
       }
       else if(c[v[i]]>c[u[i]])
       {
         dir[i]=0;
       }
       else 
       {

         a[u[i]].pb(v[i]);
         a[v[i]].pb(u[i]);
       }
    }

    rep(i,1,n+1)
    {
       if(!vis[i])
       {
         dfs(i,0);
       }
    }

    rep(i,0,m)
    {
       if(c[u[i]]==c[v[i]])
       {
         if(s.find({u[i],v[i]})!=s.end()) dir[i]=1;
         else dir[i]=0;
       }
    }

    rep(i,0,m)
    {
       if(dir[i]==1) cout<<"->"<<endl;
       else cout<<"<-"<<endl;
    }
    
      
    
    

  
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,a[1001001],dp[1001001][20],states,mod=1e9+7;
string s;
signed main()
{
	cin>>s>>k;
    int n=s.size();
    for(int i=1;i<=n;i++)
    {
        if(s[i-1]>='0'&&s[i-1]<='9')
			a[i]=s[i-1]-'0';
        else
			a[i]=s[i-1]-55;
    }
    for(int i=0;i<n;i++)
	{
        for(int j=1;j<=16; j++)
		{
            dp[i+1][j]=(dp[i+1][j]+dp[i][j]*j%mod)%mod;
            dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*(16-j)%mod)%mod;
        }
        dp[i+1][0]=(dp[i+1][0]+dp[i][0])%mod;
        dp[i+1][1]=(dp[i+1][1]+dp[i][0]*15%mod)%mod;
        for(int j=0;j<a[i+1];j++)
		{
            int ns=states;
            if(i||j)
				ns|=(1<<j);
			int tmp=0;
			for(int i=30;i>=0;i--)
				if((ns&(1<<i))>0)
					tmp++;
            dp[i+1][tmp]+=1;
        }
        states|=(1<<a[i+1]);
    }
    int tmp=0;
		for(int i=30;i>=0;i--)
			if((states&(1<<i))>0)
				tmp++;
    cout<<dp[n][k]+(k==tmp);
    return 0;
}