//ABC_199_
//
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> X(m),Y(m),Z(m);
    rep(i,m) cin >> X[i] >> Y[i] >> Z[i];
    vector<ll> dp((1<<n)+5);
    dp[0] = 1;

    rep(i,n)    
    {
        rep(bit,1<<n)
        {
            //経っているbit数が桁と一致しなければ飛ばす
            int bit_num = 0;
            rep(k,n) if((bit>>k)&1)++bit_num;
            if(bit_num != i) continue;

            //追加する数
            rep(add,n)
            {
                bool ok=true;
                if((bit>>add)&1) continue;
                //遷移先のbit
                int next_bit = bit | (1<<add);
                //next_bitへの遷移が可能かどうかMの条件を見ていく
                rep(mi,m)
                {
                    if(i+1 != X[mi]) continue;
                    //y以下でたってるビット数
                    int bit_num_y = 0;
                    rep(k,Y[mi]) if((next_bit>>k)&1)++bit_num_y;
                    //もしZ以上のbitがたっていたら遷移できない
                    if(bit_num_y>Z[mi]) ok = false;
                }
                if(ok) dp[next_bit] += dp[bit];
            }
        }
    }
    cout << dp[(1<<n)-1] << endl;



    return 0;
}
#define _USE_MATH_DEFINES
 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
constexpr ll MOD = 1000000007;

#ifndef ONLINE_JUDGE
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " (" << x.first << " : " << x.second << ")" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "["; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "]"; return o;}
ostream &operator<<(ostream &o, const string &obj) {o << "\""; o << obj.c_str(); o << "\""; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "(" << obj.first << ", " << obj.second << ")"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print_sim_py(void) {cout << endl;}
template <class Head> void print_sim_py(Head&& head) {cout << head;print_sim_py();}
template <class Head, class... Tail> void print_sim_py(Head&& head, Tail&&... tail) {cout << head << " ";print_sim_py(forward<Tail>(tail)...);}

#define print(...) print_sim_py(__VA_ARGS__);
#else
#define print(...);
#endif

template <typename... Ts>
std::istream& IN(Ts&... xs){ return (std::cin >> ... >> xs); }

#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a,b,c;
    ll ca,cb;
    IN(a,b,c);

    ca=cb=1;
    ll ans = 0;
    ll a1=a%10;
    a1=(a1*(a%10))%10;
    while(a1!=(a%10)){
        ca++;
        a1=(a1*(a%10))%10;
    }
    cb = modpow(b,c,ca);
    cb = (cb+(ca-1))%ca;
    print(ca,cb)


    ll ap=a%10;

    rep(i,cb){
        ap=(ap*(a%10))%10;
    }

    ans = ap;

    cout << ans << endl;
 
    return 0;
}

