#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#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()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll 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;

struct xyz{ll y, z;};

ll popcount(ll bit, ll N) {
    ll res = 0;
    rep(i,N) if ((bit>>i)&1) res++;
    return res;
}

int main() {
    ll N, M; cin >> N >> M;
    vector<vector<ll>> A(N,vector<ll>(N,inf));
    rep(i,M) {
        ll x, y, z; cin >> x >> y >> z;
        x--; y--;
        chmin(A[x][y],z);
    }

    vector<vector<ll>> dp(N+1,vector<ll>(1<<N));
    dp[0][0] = 1LL;
    rep(i,N) {
        rep(bit,1<<N) {
            ll cnt = popcount(bit,N);
            if (cnt!=i) continue;
            rep(j,N) {
                if ((bit>>j)&1) continue;
                ll nbit = bit | (1<<j);
                ll ncnt = 0;
                bool NG = false;
                rep(k,N) {
                    if ((nbit>>k)&1) ncnt++;
                    if (ncnt>A[i][k]) {
                        NG = true;
                        break;
                    }
                }
                if (NG) continue;
                dp[i+1][nbit] += dp[i][bit];
            }
        }
    }

    ll ans = dp[N][(1<<N)-1];

    cout << ans << endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //int:2*10**9
typedef long double ld;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define vec2(name,i,j,k) vector<vector<ll>> name(i,vector<ll>(j,k))
#define vec3(name,i,j,k,l) vector<vector<vector<ll>>> name(i,vector<vector<ll>>(j,vector<ll>(k,l)))
#define pb push_back
#define MOD 1000000007 //998244353
#define PI 3.141592653
#define INF 100000000000000 //14
//cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);


ll powe(ll a, ll b, ll mod){//aのb乗のmod
    ll ret = 1;
    while(0 < b){
        if((b%2) == 0){
            a = (a*a)%mod;
            b >>= 1;
        }
        else{
            ret = (ret*a)%mod;
            b--;
        }
    }
    return ret;
}

int main(){
    ll a, b, c; cin >> a >> b >> c;
    a%=10;
    if (a==0) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<ll>> k(10);
    REP(i,10) k[i].pb(i);
    REP(i,10) {
        ll val = (i*i)%10;
        while (val!=k[i][0]) {
            k[i].pb(val);
            val = (val*i)%10;
        }
    }
    ll cnt = k[a].size();
    ll divd = powe(b,c,cnt);
    // cout << cnt << " " << divd << " " << a << endl;
    if (divd!=0) cout << k[a][divd-1] << endl;
    else cout << k[a][k[a].size()-1] << endl;
}