#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

const int modulo=666013;

struct data{

int inceput;
int sfarsit;

}nod;

vector <data> v1;
vector <data> v2;
vector <data> v3;

vector <int >factorial;


ifstream fin("aquapark.in");
ofstream fout("aquapark.out");

void functie_daca_este_pe_interval1(int a,int b)
{
    nod.inceput=min(a,b),nod.sfarsit=max(a,b);

    for(int i=0;i<v1.size();i++)
    {
        int x=v1[i].inceput,y=v1[i].sfarsit;

        if((nod.inceput<x &&nod.sfarsit<y && x<nod.sfarsit)||(x<nod.inceput && y<nod.sfarsit &&nod.inceput <y))
        {
            v2.push_back(nod);
            return;
        }

    }

    v1.push_back(nod);

}

void functie_daca_este_pe_interval2(int a,int b)
{
    nod.inceput=min(a,b),nod.sfarsit=max(a,b);

    for(int i=0;i<v2.size();i++)
    {
        int x=v2[i].inceput,y=v2[i].sfarsit;

        if((nod.inceput<x &&nod.sfarsit<y && x<nod.sfarsit)||(x<nod.inceput && y<nod.sfarsit&&nod.inceput <y))
        {
            v3.push_back(nod);
            return;
        }

    }

    v2.push_back(nod);

}

int combinari(int k,int n)
{
    return (factorial[n]/(factorial[n-k]*factorial[k]%modulo))%modulo;
}

int main()
{
    int n,m,c,i,a,b;

    fin>>c>>n>>m;

    fin>>a>>b;

    nod.inceput=a;
    nod.sfarsit=b;

    v1.push_back(nod);

    if(c==1)
    {
        for(i=2;i<=m;i++)
        {
            fin>>a>>b;
            functie_daca_este_pe_interval1(a,b);
        }

        for(i=0;i<v1.size();i++)
            fout<<v1[i].inceput<<" "<<v1[i].sfarsit<<" "<<1<<"\n";

        for(i=0;i<v2.size();i++)
            fout<<v2[i].inceput<<" "<<v2[i].sfarsit<<" "<<2<<"\n";

    }
    else
    {
        for(i=2;i<=m;i++)
        {
            fin>>a>>b;
            functie_daca_este_pe_interval1(a,b);
        }

        for(i=0;i<v1.size();i++)
            functie_daca_este_pe_interval2(v1[i].inceput,v1[i].sfarsit);

        int val=abs(v1.size()-v3.size());

        factorial.push_back(1);

        for(i=1;i<=val;i++)
        {
            int sum=factorial[i-1]*i%modulo;

            factorial.push_back(sum);
        }

        int suma=0;

        for(i=0;i<=val;i++)
        {
            suma=(suma+combinari(i,val))%modulo;
        }


        suma=suma*2%modulo;

        fout<<suma;

    }




    return 0;
}