C++ :

#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
       
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
LL pow_mod(LL b,LL p,LL k) {
    LL res=1;
    for(;p;p>>=1) {
        if(p&1) res=res*b%k;
        b=b*b%k;
    } return res;
}
 
const int maxn=(int)(1e6)+5;
const int mo=19940417;
 
struct node {
    int x,v;
    node(int _x=0,int _v=0):x(_x),v(_v) {}
} p[maxn];
 
inline bool operator < (node a,node b) {
    if(a.x!=b.x) return a.x<b.x;return a.v<b.v;
}
 
inline bool operator == (node a,node b) {
    return a.x==b.x && a.v==b.v;
}
 
int f[maxn][2],mx[maxn][2];
 
inline void add(int& x,int v) {
    x+=v;if(x>=mo) x-=mo;
}
 
inline void chkmax(int& x,int v) {
    x=max(x,v);
}
 
int main() {
    int n,m;
    read(n);read(m);
    REP(i,1,m) {
        int x,v;
        read(x);read(v);
        p[i]=node(x,v);
    }
    ++m;p[m]=node(0,0);
    ++m;p[m]=node(n,0);
    sort(p+1,p+m+1);
    m=unique(p+1,p+m+1)-p-1;
    memset(mx,0x80,sizeof(mx));
    f[1][0]=1;mx[1][0]=0;
    REP(i,2,m) {
        int a=p[i-1].v,b=p[i].v,pa=p[i-1].x,pb=p[i].x,tmp;
 
        // f[i-1][0] => f[i][0]
 
        if(pb-pa==a-b) {
            add(f[i][0],f[i-1][0]);
            if(mx[i-1][0]>=0) {
                chkmax(mx[i][0],max(mx[i-1][0],a));
            }
        } else {
            tmp=pb-pa-a-b-2;
            if(tmp>=0) {
                add(f[i][0],f[i-1][0]*pow_mod(2,tmp/2,mo)%mo);
                if(mx[i-1][0]>=0) { 
                    chkmax(mx[i][0],max(mx[i-1][0],max(a,b+(tmp+2)/2)));
                }
            }
        }
 
        // f[i-1][0] => f[i][1]
 
        if(b) {
            tmp=pb-pa-a-b;
            if(tmp>=0) {
                add(f[i][1],f[i-1][0]*pow_mod(2,max(0,tmp/2-1),mo)%mo);
                if(mx[i-1][0]>=0) {
                    chkmax(mx[i][1],max(mx[i-1][0],max(a,max(b,tmp/2))));
                }
            }
        }
 
        // f[i-1][1] => f[i][0]
 
        tmp=(a+b+pb-pa)/2;
        if(tmp>=a && tmp>b) {
            add(f[i][0],f[i-1][1]);
            if(mx[i-1][1]>=0) {
                chkmax(mx[i][0],max(mx[i-1][1],tmp));
            }
        }
        tmp=pb-pa-a-b-2;
        if(tmp>=0) {
            add(f[i][0],f[i-1][1]*(pow_mod(2,tmp/2+1,mo)-1+mo)%mo);
            if(mx[i-1][1]>=0) {
                chkmax(mx[i][0],max(mx[i-1][1],max(a+(tmp+2)/2,b+(tmp+2)/2)));
            }
        }
 
        // f[i-1][1] => f[i][1]
 
        if(b) {
            if(pb-pa==b-a) {
                add(f[i][1],f[i-1][1]);
                if(mx[i-1][1]>=0) {
                    chkmax(mx[i][1],max(mx[i-1][1],b));
                }
            } else {
                tmp=pb-pa-a-b;
                if(tmp>=0) {
                    add(f[i][1],f[i-1][1]*pow_mod(2,tmp/2,mo)%mo);
                    if(mx[i-1][1]>=0) {
                        chkmax(mx[i][1],max(mx[i-1][1],max(a+(tmp)/2,b)));
                    }
                }
            }
        }
    }
    printf("%d %d\n",f[m][0],mx[m][0]);
    return 0;
}