//{{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VLL = vector<LL>;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

int k;
int n;
string s;

const int mod = 1e9 + 7;
inline int ch2dig(char ch)
{
    if (ch >= 'A' && ch <= 'F') return ch - 'A' + 10;
    return ch - '0';
}

const int N = 2e5 + 10;
LL dp[N][20];
LL cnt[N];

LL dfs(int pos, int st, bool bound, bool zeros)
{
    if (pos == -1) return __builtin_popcount(st) == k;

    LL ret = 0;
    if (bound && zeros)
    {
        int ed = bound ? ch2dig(s[pos]) : 15;
        for (int i = 0; i <= ed; i++)
        {
            int new_st = st;
            if (i) new_st |= (1 << i);

            ret += dfs(pos - 1, new_st, bound && i == ed, zeros && i == 0);
            ret %= mod;
        }
        debug(pos, st, bound, zeros, ret);
        return ret;
    }

    if (bound && !zeros)
    {
        int ed = bound ? ch2dig(s[pos]) : 15;
        for (int i = 0; i <= ed; i++)
        {
            int new_st = st | (1 << i);

            ret += dfs(pos - 1, new_st, bound && i == ed, 0);
            ret %= mod;
        }
        debug(pos, st, bound, zeros, ret);
        return ret;
    }

    if (!bound && zeros)
    {
        for (int i = 0; i <= 15; i++)
        {
            int new_st = st;
            if (i) new_st |= (1 << i);

            ret += dfs(pos - 1, new_st, 0, zeros && i == 0);
            ret %= mod;
        }
        debug(pos, st, bound, zeros, ret);
        return ret;
    }

    if (dp[pos][__builtin_popcount(st)] != -1) return dp[pos][__builtin_popcount(st)];
    if (!bound && !zeros)
    {
        for (int i = 0; i <= 15; i++)
        {
            int new_st = st | (1 << i);

            ret += dfs(pos - 1, new_st, 0, 0);
            ret %= mod;
        }
    }
    debug(pos, st, bound, zeros, ret);
    return dp[pos][__builtin_popcount(st)] = ret;
}

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> s >> k)
    {
        clr(dp, -1);
        n = sz(s);
        reverse(all(s));

        LL ans = dfs(n - 1, 0, 1, 1);
        cout << ans << endl;
    }

    return 0;
}
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 19;
const int MAX_M = 105;
ll dp[(1 << MAX_N)];
int X[MAX_M],Y[MAX_M],Z[MAX_M];

int main()
{
	int N,M;
	cin >> N >> M;
	rep(i,M)
	{
		cin >> X[i] >> Y[i] >> Z[i];
		//X[i] = i%(N-1)+1; Y[i] = i%(N-1)+1; Z[i] = i%N;
	}
	dp[0] = 1;
	for (int bits = 0; bits < (1 << N); ++bits)
	{
		vector<int> ppcnt(N+1,0);
		rep(i,N) {ppcnt[i+1] = ppcnt[i] + ((bits >> i) & 1);}
		/*
		rep(i,N+1) cout << ppcnt[i] << " ";
		cout << endl;
		*/
		rep(i,N)
		{
			if ((bits >> i) & 1 != 0) continue;
			bool ok = true;
			int c;
			rep(j,M)
			{
				if (i+1 <= Y[j]) c = 1;
				else c = 0;
				if (X[j] == ppcnt[N]+1 && ppcnt[Y[j]]+c > Z[j]) ok = false;
			}
			if (ok) dp[bits | (1 << i)] += dp[bits];
		}
		//cout << bits << " " << dp[bits] << endl;
	}
	cout << dp[(1 << N) - 1] << endl;
	return 0;
}