#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 100000 + 10;
const int MOD = 2000000000 + 11;
const int PRE_FACT[1001] = {1,607667727,1642217365,1624055472,94271961,147095621,1727541586,1346344892,331160101,301057891,363886615,1987124224,1409282799,368437411,593826273,333254220,509444711,1211715078,1308348013,1785902096,1817329888,983597713,1309467485,81700346,1330889160,1310220784,1533399135,1881120715,1036768739,1754894311,1401794564,337270174,1530060790,22165024,1066107203,996629994,1128623775,735135011,1949954028,300509461,1568515239,1983582649,1319728558,1095744205,929600460,1879561251,145022271,1969792247,1218693110,655080739,1340732255,
    533300461,1947525551,1478521102,197249671,555351542,1785934018,1665145136,1360156276,143617633,1841365283,403201785,1052754406,247697835,971831570,1797943549,755540885,1931894428,1443855456,1326237169,114423256,893946381,811756209,1721273350,1624436970,1728581997,1713343151,1146428215,145284135,1912257926,1710013049,1571683164,1440540865,1024038449,766572030,1664632453,1488140624,176046322,1349622707,1402597280,873111513,836373419,99914173,820650816,956225454,366027197,385979448,84856854,14966926,1492196851,422470864,
    1192713852,1007151797,111896794,1136246490,655218789,1477858728,194405702,33891945,1239338753,864841454,823799202,304629586,1952928998,194047638,1223143452,1112260403,72862482,1735842018,1857622849,949541789,1833320317,902098216,957131575,927145100,357463885,1052356684,1648405384,1488620941,1657826668,914199643,899982237,1467584533,1081211087,1028654966,1240413403,36093404,629338086,192770699,1448497415,1504834244,915822499,1333118658,445763938,863789006,1995308937,1686883307,1076090916,623925562,1962404050,451416412,
    1068059617,1295723247,587637116,84010507,1462545152,1999855139,977292738,26131657,786138296,476982384,979755693,787583020,784109512,1321513862,1773410056,868608790,136820935,926865263,1954125407,995380174,536538085,1580651344,667192394,1646307994,186246737,266288381,1762815706,1623517346,28297416,285738271,1538246212,550784498,1442070213,545303769,1685993419,11176031,1634628955,713878445,44990829,1047564421,1178076028,961681810,1548746295,805475657,1438953903,316555150,375496265,1120755947,1518955227,1730291751,
    224960766,1450113156,1322112583,132664243,1960525612,1618956031,1890643613,990996040,472351572,355963849,161753918,314101934,516249573,1686177508,1907565662,392999528,1548738638,1797860914,1325397755,679888167,1421901071,1173942802,1618371602,510043712,278022192,1622426065,849164929,1946601897,1442027289,1003626414,1168018570,1856981568,718723811,1663018952,164286470,80008788,919759524,728523007,1242669939,1968026369,1814544737,659616179,1695219879,284654431,436600787,1610685459,1478126999,1645507959,103473091,92868707,
    1011345346,720276531,1058302087,46003406,853581874,1665923094,213361772,287187218,42822096,760038547,968233569,1415439682,1357763220,1230019738,431919525,26459606,1893968204,1848331302,513811270,1341104556,1504775601,392031906,1691524854,1723822257,278712690,261726116,848348912,296678309,1723273948,517502883,1323250141,1173756477,313409677,1807264416,568615551,1118537536,463530231,1042532368,889449311,1369387807,472430845,507649244,1331595205,539653656,786745708,1081644868,758099933,1804034528,266270646,154431364,
    1055534368,285072852,1743115075,1946976724,1918578169,84721111,529763555,1855654250,533396852,1725864818,609871698,593467391,1277993896,1636187344,586008991,968094368,419889490,1442721284,553805321,396419511,1007813065,164542205,709029735,1046644771,1149489886,1492738079,1772420458,1621939396,1999475540,509976174,1175588396,1285175043,210400678,1628873132,1429989268,1137256457,1159483837,1966888060,869448093,98541368,809453089,1643538979,1946206024,684439262,34105004,472779588,215936483,573851151,1396419901,900233077,
    1417828818,1434478152,250732894,64082259,300323779,429483441,560049525,659814834,389085947,1153555724,1578029748,1662743373,1021449647,1575714581,1879721460,596044567,275258746,373677426,590816803,1185340564,828049618,953170901,418308421,448038974,1137705289,295537748,905193319,586291803,715828101,930357390,439167308,1004902980,344732486,782456235,1737199552,867593313,1736871520,130945831,213594541,1471573826,168385485,1812293291,1519116228,142301534,373490698,77632751,1300500658,139845818,1495419212,1496435175,
    1128707863,170803726,954170998,1924125210,736043784,1691488179,716672575,1845028833,1742759553,886244661,638490223,1943824353,901450921,226117453,1480123445,767185820,153421552,1799383143,469981843,637296345,1908278755,463232147,1317552887,980935067,1317394202,1349676990,683309534,1319097370,1022525583,1726165182,1345156383,1465959655,278678705,1049759927,1152035285,1504922033,818000159,303318597,1598240264,1730093463,32403940,1378980978,1379947303,190148682,1976515300,1417898810,1168261698,1946862487,1179519668,578490442,
    752782336,179188674,644413012,1151789586,758269479,1550129727,431194075,1316132182,878408667,429110182,624870282,1391739290,142149445,562175193,1369597332,1483266950,420912993,1860342381,408132828,765132821,516491759,1238483175,1282737175,1898829005,396503450,624125176,1632477809,1340260558,1485808905,320117005,41269604,841005695,540701934,33090166,397823444,21268135,1143058700,1049832218,450977953,897944102,974482715,653513143,1359995259,804668824,1311703908,686197798,1854044990,1886905395,393245465,743002378,
    974862892,1559975950,57254947,172489493,1278289079,788932257,1532895935,522258581,1469363907,529658778,1594515400,1484362829,1631477449,1682498819,561086805,1851742718,944267144,1248912772,1360699950,957369531,1457100387,1022563960,484992633,1116121174,948299172,1151241410,533040089,1338196867,1357156916,1845005758,1012843927,1821813507,1836958057,1535903759,1970719734,1899808309,1183916145,207210835,1916556153,1397870096,1243769897,1987193060,1570028797,305201068,1869791081,1032891226,1675073566,1449004085,487768007,1585396968,
    203389978,84534865,1594807073,347079741,1017670282,775337520,1807474133,269150058,1533766819,234589924,475093169,1074040345,1266172527,1241491645,215946448,1518306050,1480178269,1333706505,1936222939,885803942,1666691558,548097364,1337945981,1747408764,1407899180,1941498288,544413468,69699034,291983834,1027280954,466481538,1974676952,612921624,349553845,922936044,836982326,859438639,886709168,534292189,6875812,112210373,1397876673,1957951622,1510443638,1305327258,749500589,1560142089,53111869,1425899680,33345696,
    837662786,1300114081,139328482,1156877381,1590195901,1962037159,437880403,1420885026,1526987474,1670035332,1568663158,1363461563,867893051,373456104,871456090,1618441318,821750736,207345047,1762625722,1389600544,1907915038,387370996,877026491,1658303833,1010086048,1405411138,1790276212,968873234,1132331781,1926213560,867847061,1725589553,213822218,1051633919,85520238,1025320964,1118851678,1781034992,107391620,103938049,833027130,141963699,1558084778,428389480,1133465639,182713568,712780897,1078703653,245001141,162569644,
    1780001542,1489982273,706705140,883598548,1447120979,1839721644,632956766,1734939669,267481371,1335168605,792922881,1272071464,1293996389,996980981,1778864945,1133559067,1308169736,142475368,1809160284,817594857,965119133,720987022,1980922134,801359010,541078383,574895095,1072663348,1135468279,1873813740,1828700932,1458275221,1869158230,632307269,998226890,1958052575,1607212652,829462100,620272574,1012321802,1865810284,788009880,1583283820,699515475,1816838004,1443160713,23633921,453044333,1310613906,879692538,903071326,
    1620274954,153553016,80896513,1002697578,1022717930,258156845,1564735989,96459230,95180777,151733460,339267131,1012396824,555513461,342090189,512273843,1722495033,1580002094,1225260863,675021125,563082174,160664196,1597193647,1747969524,238158033,773734328,483231273,1434698727,357750605,1418047134,572353793,895081193,859274992,1677326655,101550311,314958439,965539059,383927412,987917115,945005041,1047303909,1648603316,1576624857,1743369512,1953822549,594082126,1483085265,1091550667,1877827897,698708447,1916054910,
    1057039862,552987668,451607186,1204916963,383662233,1204867538,1136361683,1967555972,533981870,144050002,1643374051,1769974603,566667538,1535745785,1253385028,1208225598,1227362587,1451218740,1735314746,1694197549,22699232,899826862,1639503654,57862589,817164608,153643884,1417341329,987362196,61759636,1651633766,578002133,1911392484,614158226,1026976343,656677752,205464791,868465439,510232400,1182739771,867896551,866721598,1989171355,930737169,1736159171,1445543349,1591868645,741284395,794925000,1177071404,194680075,
    322592688,1271979246,1245965875,1072182618,1503762512,718460994,1105451879,647451230,1835270294,349487732,29030959,290645482,614784099,1456444933,1696923064,1719096234,1222701132,1834583378,260422809,1162635753,139551447,1563048260,1542551789,534363145,598641167,1085451060,278544960,328812752,1375407419,1408150319,259022933,950685755,1237948189,170755310,418766553,1576403392,681674361,1495416753,698496494,851803404,215441000,1965786471,593215519,713565615,1985823890,1553262309,108185831,328223772,833746135,1027960630,
    329102740,356694113,321248076,1085253475,1137484858,1189714107,1945446811,89106774,1620893451,1940461284,54976270,902265802,923098859,160391234,68979373,798105100,1073998783,360032653,773234032,1807815531,1055373161,125010994,1924063389,547064827,1133815847,189125314,518719358,1240114644,562076927,161122063,706209979,1032364725,1159698462,1229732772,1113754305,195607534,341112594,952360318,966949473,1905248264,767994256,1793793391,463901690,963468346,490226074,783596876,1729008137,83159259,205791513,151211130,
    41279625,1453377230,223520667,1907645142,28498758,835571782,236394088,1276391068,1849113057,1041016634,1786706219,1721954730,127028616,530318791,91539069,1800075485,338787233,1219632324,1440728054,4574566,325446350,474720981,416329643,21426265,920928994,1594752589,1133634221,1479832641,311261032,1181766896,1562219694,1160760266,896523140,1484263021,239165362,1349143833,1156900053,232716746,76236670,426106079,1649048322,1117443465,747571269,296246686,5804222,674181450,1607276001,1353797562,521842864,111085282,
                            1504997667,180904022,761271585,1042303639,1140522853,1298375082,501872888,1406497781,98247344,585472563,38380901,1653138130,1644356754,28677626,277530925,268371194,822903225,1454113281,896420058,1523389384,126513659,1023755135,1149446517,203634379,675082017,828963142,597645447,829867076,1952986960,1369130124,1389431213,1093444802,490412402,1779080629,175902425,1835709882,331697776,645659162,687504180,317922887,1648686935,60642870,1632758634,845528756,1228419804,304837551,321009011,618197247,1498558757,893121698};

int dp[3], tr[3][3], dp2[3];
int n, m, minSuf[MAXN];
int a[MAXN], b[MAXN];
map<int, int> pre;
map<int, bool> used;

int getFact (int n) {
    int ret = PRE_FACT[n / 1000000];
    for(int i = n / 1000000 * 1000000 + 1; i <= n; i++)
        ret = ret * 1LL * i % MOD;
    return ret;
}

void update (int& a, int b) {
    a = (a * 1LL + b) % MOD;
}

int getMinSuf (int x) {
    if (x > n)
        return n + 1;
    int p = (int)(lower_bound(a + 1, a + m + 2, x) - a);
    return minSuf[p];
}

void makeStep (int i) {
    dp2[0] = dp2[1] = dp2[2] = 0;
    int preI = pre[i];
    for(int j = 0; j < 3; j++)
        if (preI == 0) {
            if ((j & 2) == 0 && i + 2 <= n && !used[i + 2]) update(dp2[2], dp[j]);
            if ((j & 2) == 0 && i + 1 <= n && !used[i + 1]) update(dp2[1], dp[j]);
            if (j == 0 && !used[i]) update(dp2[j], dp[j]);
            if (getMinSuf(i + 1) >= i && j) update(dp2[j >> 1], dp[j]);
        } else {
            if (preI == i + 2 && (j & 2) == 0) update(dp2[2], dp[j]);
            if (preI == i + 1 && (j & 2) == 0) update(dp2[1], dp[j]);
            if (preI == i && j == 0) update(dp2[0], dp[0]);
            if (preI < i) update(dp2[j >> 1], dp[j]);
        }
    dp[0] = dp2[0], dp[1] = dp2[1], dp[2] = dp2[2];
}

void doBrute (int q) {
    int l = a[q - 1];
    int r = a[q];
    //cerr << "brute " << q << " " << l << " " << r << endl;
    for(int i = l + 1; i <= r; i++)
        makeStep(i);
}

void mulMatrix (int a[3][3], int b[3][3], int c[3][3]) {
    int d[3][3];
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            d[i][j] = 0;
    for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) {
        d[i][j] = 0;
        for(int k = 0; k < 3; k++) {
            update(d[i][j], a[i][k] * 1LL * b[k][j] % MOD);
        }
    }
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i][j] = d[i][j];
}

void getPower (int matr[3][3], int power) {
    int rt[3][3];
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            rt[i][j] = (i == j);
    for(int i = 0; (1 << i) <= power; i++) {
        if (power & (1 << i)) {
            mulMatrix(rt, matr, rt);
        }
        mulMatrix(matr, matr, matr);
    }
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            matr[i][j] = rt[i][j];
}

void mulVector (int a[3], int b[3][3]) {
    int c[3];
    c[0] = c[1] = c[2] = 0;
    for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++)
        update(c[j], a[i] * 1LL * b[i][j] % MOD);
    for(int i = 0; i < 3; i++)
        a[i] = c[i];
}

void transit (int q) {
    
    int l = a[q - 1];
    int r = a[q] - 3;
    
    if (l > r) {
        doBrute(q);
        return ;
    }
    
    int k1 = 0, k2 = 0;
    
    int s = getMinSuf(l + 1);
    
    if (s >= r) {
        k1 = r - l;
        k2 = 0;
    } else if (s < l) {
        k1 = 0;
        k2 = r - l;
    } else {
        k1 = s - l + 1;
        k2 = r - l - k1;
    }
    
    //cerr << "q = " << q << " k1 = " << k1 << " k2 = " << k2 << " " << l << " " << r  << " " << s << " " << n << endl;
    
    if (k1 > 0) {
        for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) tr[i][j] = 0;
        for(int j = 0; j < 3; j++) {
            if ((j & 2) == 0) tr[j][2]++;
            if ((j & 2) == 0) tr[j][1]++;
            if (j == 0) tr[j][j]++;
            if (j) tr[j][j >> 1]++;
        }
        getPower(tr, k1);
        mulVector(dp, tr);
    }
    
    if (k2 > 0) {
        for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) tr[i][j] = 0;
        for(int j = 0; j < 3; j++) {
            if ((j & 2) == 0) tr[j][2]++;
            if ((j & 2) == 0) tr[j][1]++;
            if (j == 0) tr[j][j]++;
        }
        getPower(tr, k2);
        mulVector(dp, tr);
    }
    for(int i = r + 1; i <= a[q]; i++)
        makeStep(i);
}

int main () {
//    freopen("input.txt", "r", stdin);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        pre.clear();
        cin >> n >> m;
        int preDef = 0;
        
        dp[0] = dp[1] = dp[2] = 0;
        pre.clear();
        used.clear();
        
        bool fail = false;
        bool noBadVectors = false;
        for(int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            if (!pre.count(y))
                pre[y] = 0;
            if (!pre.count(y+1) && y+1 <= n)
                pre[y+1] = 0;
            if (!pre.count(y+2) && y+2 <= n)
                pre[y+2] = 0;

            
            if ((pre[x] != 0 && pre[x] != y) || (used[y] && pre[x] != y)) {
                fail = true;
            } else if (y > x + 2) {
                noBadVectors = true;
            }
            preDef += (pre[x] == 0);
            pre[x] = y;
            used[y] = true;
        }
        
        if (fail) {
            cout << 0 << endl;
            continue;
        }
        
        if (n == 1) {
            cout << 0 << endl;
            continue;
        }
        
        if (noBadVectors) {
            cout << getFact(n - preDef) << endl;
            continue;
        }
        
        m = 0;
        for(map<int, int>::iterator it = pre.begin(); it != pre.end(); ++it) {
            ++m;
            a[m] = it->first;
            b[m] = it->second;
        }
        
        a[m + 1] = n;
        minSuf[m + 1] = n + 1;
        for(int i = m; i > 0; i--)
            if (b[i] != 0)
                minSuf[i] = min(minSuf[i + 1], b[i]);
            else
                minSuf[i] = minSuf[i + 1];
        
        
        
        dp[0] = 1;
        dp[1] = dp[2] = 0;
        
        for(int i = 1; i <= m + 1; i++) {
            transit(i);
        }
        
        cout << (getFact(n - preDef) * 1LL + MOD - dp[0]) % MOD << endl;
        
    }
    
    return 0;
}