import std.stdio, std.string, std.conv, std.algorithm;

void main()
{
    auto f = readln.split.map!(to!int);
    int N = f[0],
        K = f[1];
    int[100] pasta;
    foreach(i; 0 .. K)
    {
        auto g = readln.split.map!(to!int);
        pasta[g[0] - 1] = g[1];
    }

    ulong calc(int i)
    {
        if(i == N)
        {
            return 1;
        }
        else if(pasta[i] == 0)
        {
            ulong res;
            foreach(n; 1 .. 4)
            {
                if(
                       i >= 2               && pasta[i - 1] == n && pasta[i - 2] == n
                    || i >= 1 && i <= N - 2 && pasta[i - 1] == n && pasta[i + 1] == n
                    || i <= N - 3           && pasta[i + 1] == n && pasta[i + 2] == n
                )
                {
                    continue;
                }
                pasta[i] = n;
                res += calc(i + 1);
            }
            pasta[i] = 0;
            return res;
        }
        else
        {
            return calc(i + 1);
        }
    }

    writeln(calc(0) % 10_000);
}