#include <bits/stdc++.h>

using namespace std;

template<typename T>
istream &operator>>(istream &in, vector<T> &x) {
    for (auto &i : x)
        in >> i;
    return in;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &x) {
    for (auto &i : x) {
        out << i << " ";
    }
    return out;
}

template<typename T, typename D>
istream &operator>>(istream &in, pair<T, D> &x) {
    in >> x.first >> x.second;
    return in;
}

template<typename T, typename D>
ostream &operator<<(ostream &out, const pair<T, D> &x) {
    out << x.first << " " << x.second;
    return out;
}

struct LogOutput {
    template<typename T>
    LogOutput &operator<<(T x) {
#ifdef Dmitry07
        cout << x;
#endif
        return *this;
    }
} dout;

typedef long long ll;
typedef unsigned long long ull;
typedef double dl;

#define nl '\n'
#define elif else if
#define all(_v) _v.begin(), _v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)(v.size())
#define sqr(_v) ((_v) * (_v))
#define vpi vector<pair<int, int>>
#define eb emplace_back
#define pb push_back
// #define MOD1(x, m) ((x) % m + ((x) < 0  && ((x % m) != 0) ? m : 0))
#define mod(x, m) (((x) % (m) + (m)) % (m))
#define vi vector<int>
#define pi pair<int, int>
#define ti tupMXle<int, int, int>
#define minq(x, y) x = min((x), (y))
#define maxq(x, y) x = max((x), (y))
#define forn(i, n) for (int i = 0; i < (n); ++i)

const ll INFL = 1e15;  // 9187201950435737471;
const ll nINFL = -9187201950435737472;
const int INF = 1e9 + 10;  // 2139062143;
const int nINF = -2139062144;
const ull ULINF = numeric_limits<ull>::max();
const dl PI = acos(-1);
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);

inline void IO() {
#ifdef Dmitry07
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);
}

const int MAXN = 1e5 + 10;
const int MAXE = 1e5 + 10;
const int MOD = 1e9 + 9;
const double EPS = 1e-9;
const int W = 1e6 + 100;
const int K = 1000 + 1;

// #define int ll

vpi g[MAXN];
int col[MAXN], colOfParEdge[MAXN], par[MAXN], n;
char used[MAXN];

void dfs(int v) {
    used[v] = 1;
    if (v) {
        if (col[par[v]] == colOfParEdge[v]) {
            col[v] = col[par[v]] % n + 1;
        } else {
            col[v] = colOfParEdge[v];
        }
    }
    for (auto[to, c] : g[v]) {
        if (!used[to]) {
            colOfParEdge[to] = c;
            par[to] = v;
            dfs(to);
        }
    }
}

void Solve() {
    int m;
    cin >> n >> m;
    forn (i, m) {
        int v, u, c;
        cin >> v >> u >> c;
        v--;
        u--;
        g[v].pb({u, c});
        g[u].pb({v, c});
    }
    col[0] = 1;
    dfs(0);
    forn (i, n) {
        cout << col[i] << nl;
    }
}

signed main() {
    IO();
    int t = 1;
//    cin >> t;
    int startTime = clock();
    while (t--) {
        Solve();
    }
    int endTime = clock();
    dout << '\n' << "Time: " << (endTime - startTime) / 1000.0;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------

string N;
int K;

ll pat[202020][17];


const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K;
	int mask=0;
	
	FOR(i,N.size()) {
		char c=N[i];
		if(c>='A'&&c<='F') y=10+c-'A';
		else y=(c-'0');
		
		//初
		if(i) {
			pat[i+1][1]+=15;
		}
		//less
		FOR(j,y) {
			if(i==0&&j==0) continue;
			int mask2=mask|(1<<j);
			x=__builtin_popcount(mask2);
			pat[i+1][x]++;
		}
		//any
		FOR(x,17) {
			(pat[i+1][x]+=pat[i][x]*x)%=mo;
			if(x<16) (pat[i+1][x+1]+=pat[i][x]*(16-x))%=mo;
		}
		
		mask|=(1<<y);
	}
	
	
	ll ret=pat[N.size()][K];
	if(__builtin_popcount(mask)==K) ret++;
	
	
	cout<<ret%mo<<endl;
	
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}
