#include <bits/stdc++.h>
using namespace std;
const int maxn = 22;
const int p3maxn = 10000000;

int RGB(char a) {
    switch(a) {
        case 'R':
            return 0;
        case 'G':
            return 1;
        case 'B':
            return 2;
        default:
            __builtin_unreachable();
    }
}

int color[maxn];
int p3[maxn];
int pre[3][p3maxn];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<tuple<int,int,int,int>> edge;
    for (int i = 0; i < M; i++) {
        int a, b;
        char cc, cd;
        cin >> a >> cc >> b >> cd;
        --a, --b;
        int c = RGB(cc);
        int d = RGB(cd);
        edge.emplace_back(a, c, b, d);
    }
    for (int i = 0; i < N; i++)
        color[i] = -1;
    if (N <= 8) {
        int ans = 0;
        auto dfs = [&](auto self, int i) {
            if (i == N) {
                bool ok = true;
                for (auto [a, c, b, d]: edge) {
                    if (color[a] == c && color[b] == d) {
                        ok = false;
                        break;
                    }
                }
                if (ok)
                    ++ans;
                return;
            }
            for (int j = 0; j < 3; j++) {
                color[i] = j;
                self(self, i+1);
                color[i] = -1;
            }
        };
        dfs(dfs, 0);
        cout << ans << '\n';
        return 0;
    }

    const int A = 9, B = N - A;
    p3[0] = 1;
    for (int i = 1; i <= B; i++)
        p3[i] = p3[i-1] * 3;
    for (int rot = 0; rot < 3; rot++) {
        // enumerate B
        // [A, N)
        auto dfs = [&](auto self, int i, int code) {
            if (i == N) {
                bool ok = true;
                for (auto [a, c, b, d]: edge) {
                    if (color[a] == c && color[b] == d) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    pre[rot][code] += 1;
                }
                return;
            }
            for (int j = 0; j < 3; j++) {
                color[i] = j;
                self(self, i+1, code * 3 + j);
                color[i] = -1;
            }
        };
        dfs(dfs, A, 0);

        for (int i = 0; i < B; i++) {
            for (int s = 0; s < p3[B]; s++) {
                if (s / p3[i] % 3 != 0) {
                    pre[rot][s] += pre[rot][s - p3[i]];
                }
            }
        }
        for (auto &[a, c, b, d]: edge) {
            c = (c+1) % 3;
            d = (d+1) % 3;
        }
    }


    const auto query = [&](int p[], vector<int> &mask) -> int64_t {
        for (int j = 0; j < B; j++) {
            if (mask[j] == 0)
                return 0;
        }

        int64_t ans = 0;
        auto dfs = [&](auto self, int i, int code, int coef) {
            if (i == B) {
                ans += coef * p[code];
                return;
            }
            if (mask[i] == 5) {
                self(self, i+1, code * 3 + 2, coef);
                self(self, i+1, code * 3 + 1, -coef);
                self(self, i+1, code * 3 + 0, coef);
            } else {
                int l = __lg(mask[i] & -mask[i]);
                int r = __lg(mask[i]);
                self(self, i+1, code * 3 + r, coef);
                if (l)
                    self(self, i+1, code * 3 + l-1, -coef);
            }
        };
        dfs(dfs, 0, 0, 1);
        return ans;
    };

    {
        int64_t ans = 0;
        auto dfs = [&](auto self, int i) {
            if (i == A) {
                bool ok = true;
                vector<int> mask(B, 7);
                for (auto [a, c, b, d]: edge) {
                    if (color[a] == c && color[b] == d) {
                        ok = false;
                        break;
                    }
                    if (a < A && b >= A && color[a] == c) {
                        mask[b - A] &= ~(1 << d);
                    }
                }
                if (ok) {
                    int mn = 1e9;
                    int mnRot = -1;
                    for (int rot = 0; rot < 3; rot++) {
                        int cnt = 0;
                        for (int j = 0; j < B; j++) {
                            if (mask[j] == 5)
                                ++cnt;
                        }
                        if (mn > cnt) {
                            mn = cnt;
                            mnRot = rot;
                        }
                        for (int j = 0; j < B; j++) {
                            mask[j] <<= 1;
                            mask[j] |= mask[j] >> 3;
                            mask[j] &= 7;
                        }
                    }
                    assert (mnRot != -1);
                    for (int rot = 0; rot < mnRot; rot++) {
                        for (int j = 0; j < B; j++) {
                            mask[j] <<= 1;
                            mask[j] |= mask[j] >> 3;
                            mask[j] &= 7;
                        }
                    }
                    ans += query(pre[mnRot], mask);
                }
                return;
            }
            for (int j = 0; j < 3; j++) {
                color[i] = j;
                self(self, i+1);
                color[i] = -1;
            }
        };
        dfs(dfs, 0);
        cout << ans << '\n';
    }
}