/*
ID: tiendao1
LANG: C++
TASK: game1
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include <sstream>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<bitset>
#include<climits>
#include <list>
#include <functional>
#include <cmath>
#include <ctime>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 1e9
#define linf 1e18
#define EPS 1e-5
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define ms(x,val) memset(x, val, sizeof(x))
#define pb(x) push_back(x)
#define make_unique(x) sort(ALL(x)) ; x.erase( unique(ALL(x)), x.end()) ;
const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc()
{
if (rsz <= 0)
{
ptr = 0;
rsz = fread(bf, 1, bfsz, stdin);
if (rsz <= 0) return EOF;
} --rsz;
return bf[ptr++];
}
void ga(char &c)
{
c = EOF;
while (!isalpha(c)) c = gc();
}
int gs(char s[])
{
int l = 0;
char c = gc();
while (isspace(c)) c = gc();
while (c != EOF && !isspace(c))
{
s[l++] = c;
c = gc();
}
s[l] = '\0';
return l;
}
template<class T> bool gi(T &v)
{
v = 0;
char c = gc();
while (c != EOF && c != '-' && !isdigit(c)) c = gc();
if (c == EOF) return false;
bool neg = c == '-';
if (neg) c = gc();
while (isdigit(c))
{
v = v * 10 + c - '0';
c = gc();
}
if (neg) v = -v;
return true;
}
long long gcd(long long x, long long y)
{
return y == 0 ? x : gcd(y, x % y);
}
int toInt(char xx)
{
return xx - '0';
}
int exitInput = 0;
int ntest = 1, itest = 1 ;
void read() ;
void solve() ;
int main()
{
#ifndef ONLINE_JUDGE
//freopen("game1.in","r",stdin) ;freopen("game1.out", "w", stdout);
freopen("gentest.txt", "r", stdin);
freopen("output.txt", "w", stdout);
clock_t t1, t2 ;
//t1 = clock() ;
#endif
ios_base::sync_with_stdio(0) ;
//cin >> ntest;
//scanf("%d",&ntest) ;
//gi(ntest) ;
for (itest = 1; itest <= ntest ; ++itest)
for (itest = 1; ; ++itest)
{
read();
if (exitInput)
{
break;
}
if(itest > 1)
{
//printf("\n") ;
//cout << endl ;
}
//cout << "Case " << itest << ": ";
//printf("Case #%d\n",itest) ;
solve();
}
#ifndef ONLINE_JUDGE
//t2 = clock() ;printf("\nRunning time : %.6f\n",((float)t2 - (float)t1) / CLOCKS_PER_SEC) ;
#endif
return 0;
}
/*** IMPLEMENTATION ***/
const int dx[4] = { -1, 1, -2, 2 };
const int dy[4] = { 2, -2, -1, 1 };
const ll Mod = 1e8;
const int maxn = 100 + 5 ;
int n, m ;
pii a[maxn] ;
int f[2*maxn][2*maxn] ;
vector<int> rrh ;
int hasZero, hasN ;
int dp(int L, int R)
{
int &ref = f[L][R] ;
if(ref != -1)
{
return ref ;
}
ref = 0 ;
int i, lo, hi ;
for(i = 0; i < m; ++i)
{
lo = a[i].fi ; hi = a[i].se ;
if(lo < L && L <= hi && hi < R)
{
if(lo == 1)
{
ref += 1 ;
}
else
{
ref += dp(lo,min(hi,L)) ;
}
}
ref %= Mod ;
}
return ref ;
}
void read()
{
#define endread { exitInput = 1 ; return ; }
rrh.clear();
cin >> n >> m ; if(n + m == 0) endread ;
hasZero = hasN = 0 ;
rrh.pb(n);
for(int i = 0; i < m; ++i)
{
cin >> a[i].fi >> a[i].se ;
if(a[i].fi == 0) hasZero = 1 ;
if(a[i].se == n) hasN = 1 ;
rrh.pb(a[i].fi); rrh.pb(a[i].se);
}
make_unique(rrh);
n = 1 + lower_bound(ALL(rrh),n)-rrh.begin();
for(int i = 0; i < m; ++i)
{
a[i].fi = 1 + lower_bound(ALL(rrh),a[i].fi)-rrh.begin();
a[i].se = 1 + lower_bound(ALL(rrh),a[i].se)-rrh.begin();
}
// printf("n = %d\n",n);
// for(int i = 0; i < m; ++i)
// {
// printf("i = %d, fi = %d, se = %d\n",i,a[i].fi,a[i].se);
// }
}
void solve()
{
if(!hasZero || !hasN)
{
puts("0");
return ;
}
ms(f,-1) ;
int res = 0, i, lo, hi ;
for(i = 0; i < m; ++i)
{
lo = a[i].fi ; hi = a[i].se ;
if(lo == 1)
{
f[lo][hi] = 1;
}
}
for(i = 0; i < m; ++i)
{
lo = a[i].fi ; hi = a[i].se ;
if(hi == n)
{
res += dp(lo,hi) ;
res %= Mod ;
}
}
printf("%d\n",res) ;
}
LyoKCUlEOiB0aWVuZGFvMQoJTEFORzogQysrCglUQVNLOiBnYW1lMQoqLwoKLy8jaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8bWFwPgojaW5jbHVkZTxzZXQ+CiNpbmNsdWRlPGRlcXVlPgojaW5jbHVkZTxxdWV1ZT4KI2luY2x1ZGU8c3RhY2s+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTxjc3RkbGliPgojaW5jbHVkZTxiaXRzZXQ+CiNpbmNsdWRlPGNsaW1pdHM+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDx1dGlsaXR5PgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKI2RlZmluZSBpbmYgMWU5CiNkZWZpbmUgbGluZiAxZTE4CiNkZWZpbmUgRVBTIDFlLTUKI2RlZmluZSBQSSBhY29zKC0xKQojZGVmaW5lIHBpaSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBBTEwoeCkgKHgpLmJlZ2luKCksICh4KS5lbmQoKQojZGVmaW5lIG1zKHgsdmFsKSBtZW1zZXQoeCwgdmFsLCBzaXplb2YoeCkpCiNkZWZpbmUgcGIoeCkgcHVzaF9iYWNrKHgpCiNkZWZpbmUgbWFrZV91bmlxdWUoeCkgc29ydChBTEwoeCkpIDsgeC5lcmFzZSggdW5pcXVlKEFMTCh4KSksIHguZW5kKCkpIDsKCmNvbnN0IGludCBiZnN6ID0gMSA8PCAxNjsKY2hhciBiZltiZnN6ICsgNV07CmludCByc3ogPSAwOwppbnQgcHRyID0gMDsKY2hhciBnYygpCnsKICAgIGlmIChyc3ogPD0gMCkKICAgIHsKICAgICAgICBwdHIgPSAwOwogICAgICAgIHJzeiA9IGZyZWFkKGJmLCAxLCBiZnN6LCBzdGRpbik7CiAgICAgICAgaWYgKHJzeiA8PSAwKSByZXR1cm4gRU9GOwogICAgfSAtLXJzejsKICAgIHJldHVybiBiZltwdHIrK107Cn0Kdm9pZCBnYShjaGFyICZjKQp7CiAgICBjID0gRU9GOwogICAgd2hpbGUgKCFpc2FscGhhKGMpKSBjID0gZ2MoKTsKfQppbnQgZ3MoY2hhciBzW10pCnsKICAgIGludCBsID0gMDsKICAgIGNoYXIgYyA9IGdjKCk7CiAgICB3aGlsZSAoaXNzcGFjZShjKSkgYyA9IGdjKCk7CiAgICB3aGlsZSAoYyAhPSBFT0YgJiYgIWlzc3BhY2UoYykpCiAgICB7CiAgICAgICAgc1tsKytdID0gYzsKICAgICAgICBjID0gZ2MoKTsKICAgIH0KICAgIHNbbF0gPSAnXDAnOwogICAgcmV0dXJuIGw7Cn0KdGVtcGxhdGU8Y2xhc3MgVD4gYm9vbCBnaShUICZ2KQp7CiAgICB2ID0gMDsKICAgIGNoYXIgYyA9IGdjKCk7CiAgICB3aGlsZSAoYyAhPSBFT0YgJiYgYyAhPSAnLScgJiYgIWlzZGlnaXQoYykpIGMgPSBnYygpOwogICAgaWYgKGMgPT0gRU9GKSByZXR1cm4gZmFsc2U7CiAgICBib29sIG5lZyA9IGMgPT0gJy0nOwogICAgaWYgKG5lZykgYyA9IGdjKCk7CiAgICB3aGlsZSAoaXNkaWdpdChjKSkKICAgIHsKICAgICAgICB2ID0gdiAqIDEwICsgYyAtICcwJzsKICAgICAgICBjID0gZ2MoKTsKICAgIH0KICAgIGlmIChuZWcpIHYgPSAtdjsKICAgIHJldHVybiB0cnVlOwp9Cgpsb25nIGxvbmcgZ2NkKGxvbmcgbG9uZyB4LCBsb25nIGxvbmcgeSkKewogICAgcmV0dXJuIHkgPT0gMCA/IHggOiBnY2QoeSwgeCAlIHkpOwp9CmludCB0b0ludChjaGFyIHh4KQp7CiAgICByZXR1cm4geHggLSAnMCc7Cn0KCmludCBleGl0SW5wdXQgPSAwOwppbnQgbnRlc3QgPSAxLCBpdGVzdCA9IDEgOwoKdm9pZCByZWFkKCkgOwp2b2lkIHNvbHZlKCkgOwoKaW50IG1haW4oKQp7CgojaWZuZGVmIE9OTElORV9KVURHRQogICAgLy9mcmVvcGVuKCJnYW1lMS5pbiIsInIiLHN0ZGluKSA7ZnJlb3BlbigiZ2FtZTEub3V0IiwgInciLCBzdGRvdXQpOwogICAgZnJlb3BlbigiZ2VudGVzdC50eHQiLCAiciIsIHN0ZGluKTsKICAgIGZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICBjbG9ja190IHQxLCB0MiA7CiAgICAvL3QxID0gY2xvY2soKSA7CiNlbmRpZgogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKSA7CgogICAgLy9jaW4gPj4gbnRlc3Q7CiAgICAvL3NjYW5mKCIlZCIsJm50ZXN0KSA7CiAgICAvL2dpKG50ZXN0KSA7CgogICAgZm9yIChpdGVzdCA9IDE7IGl0ZXN0IDw9IG50ZXN0IDsgKytpdGVzdCkKICAgICAgICBmb3IgKGl0ZXN0ID0gMTsgOyArK2l0ZXN0KQogICAgICAgIHsKICAgICAgICAgICAgcmVhZCgpOwogICAgICAgICAgICBpZiAoZXhpdElucHV0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZihpdGVzdCA+IDEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vcHJpbnRmKCJcbiIpIDsKICAgICAgICAgICAgICAgIC8vY291dCA8PCBlbmRsIDsKICAgICAgICAgICAgfQogICAgICAgICAgICAvL2NvdXQgPDwgIkNhc2UgIiA8PCBpdGVzdCA8PCAiOiAiOwogICAgICAgICAgICAvL3ByaW50ZigiQ2FzZSAjJWRcbiIsaXRlc3QpIDsKICAgICAgICAgICAgc29sdmUoKTsKCiAgICAgICAgfQoKI2lmbmRlZiBPTkxJTkVfSlVER0UKICAgIC8vdDIgPSBjbG9jaygpIDtwcmludGYoIlxuUnVubmluZyB0aW1lIDogJS42ZlxuIiwoKGZsb2F0KXQyIC0gKGZsb2F0KXQxKSAvIENMT0NLU19QRVJfU0VDKSA7CiNlbmRpZgogICAgcmV0dXJuIDA7Cn0KCgovKioqIElNUExFTUVOVEFUSU9OICoqKi8KY29uc3QgaW50IGR4WzRdID0geyAtMSwgMSwgLTIsIDIgfTsKY29uc3QgaW50IGR5WzRdID0geyAyLCAtMiwgLTEsIDEgfTsKY29uc3QgbGwgTW9kID0gMWU4Owpjb25zdCBpbnQgbWF4biA9IDEwMCArIDUgOwoKaW50IG4sIG0gOwpwaWkgYVttYXhuXSA7CmludCBmWzIqbWF4bl1bMiptYXhuXSA7CnZlY3RvcjxpbnQ+IHJyaCA7CmludCBoYXNaZXJvLCBoYXNOIDsKCmludCBkcChpbnQgTCwgaW50IFIpCnsKICAgIGludCAmcmVmID0gZltMXVtSXSA7CiAgICBpZihyZWYgIT0gLTEpCiAgICB7CiAgICAgICAgcmV0dXJuIHJlZiA7CiAgICB9CiAgICByZWYgPSAwIDsKICAgIGludCBpLCBsbywgaGkgOwoKICAgIGZvcihpID0gMDsgaSA8IG07ICsraSkKICAgIHsKICAgICAgICBsbyA9IGFbaV0uZmkgOyBoaSA9IGFbaV0uc2UgOwoKICAgICAgICBpZihsbyA8IEwgJiYgTCA8PSBoaSAmJiBoaSA8IFIpCiAgICAgICAgewogICAgICAgICAgICBpZihsbyA9PSAxKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZWYgKz0gMSA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZWYgKz0gZHAobG8sbWluKGhpLEwpKSA7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmVmICU9IE1vZCA7CiAgICB9CiAgICByZXR1cm4gcmVmIDsKfQoKdm9pZCByZWFkKCkKewojZGVmaW5lIGVuZHJlYWQgeyBleGl0SW5wdXQgPSAxIDsgcmV0dXJuIDsgfQogICAgcnJoLmNsZWFyKCk7CiAgICBjaW4gPj4gbiA+PiBtIDsgaWYobiArIG0gPT0gMCkgZW5kcmVhZCA7CgogICAgaGFzWmVybyA9IGhhc04gPSAwIDsKCiAgICBycmgucGIobik7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgKytpKQogICAgewogICAgICAgIGNpbiA+PiBhW2ldLmZpID4+IGFbaV0uc2UgOwogICAgICAgIGlmKGFbaV0uZmkgPT0gMCkgaGFzWmVybyA9IDEgOwogICAgICAgIGlmKGFbaV0uc2UgPT0gbikgaGFzTiA9IDEgOwoKICAgICAgICBycmgucGIoYVtpXS5maSk7IHJyaC5wYihhW2ldLnNlKTsKICAgIH0KICAgIG1ha2VfdW5pcXVlKHJyaCk7CiAgICBuID0gMSArIGxvd2VyX2JvdW5kKEFMTChycmgpLG4pLXJyaC5iZWdpbigpOwogICAgZm9yKGludCBpID0gMDsgaSA8IG07ICsraSkKICAgIHsKICAgICAgICBhW2ldLmZpID0gMSArIGxvd2VyX2JvdW5kKEFMTChycmgpLGFbaV0uZmkpLXJyaC5iZWdpbigpOwogICAgICAgIGFbaV0uc2UgPSAxICsgbG93ZXJfYm91bmQoQUxMKHJyaCksYVtpXS5zZSktcnJoLmJlZ2luKCk7CiAgICB9CgovLyAgICBwcmludGYoIm4gPSAlZFxuIixuKTsKLy8gICAgZm9yKGludCBpID0gMDsgaSA8IG07ICsraSkKLy8gICAgewovLyAgICAgICAgcHJpbnRmKCJpID0gJWQsIGZpID0gJWQsIHNlID0gJWRcbiIsaSxhW2ldLmZpLGFbaV0uc2UpOwovLyAgICB9Cgp9Cgp2b2lkIHNvbHZlKCkKewogICAgaWYoIWhhc1plcm8gfHwgIWhhc04pCiAgICB7CiAgICAgICAgcHV0cygiMCIpOwogICAgICAgIHJldHVybiA7CiAgICB9CiAgICBtcyhmLC0xKSA7CiAgICBpbnQgcmVzID0gMCwgaSwgbG8sIGhpIDsKICAgIGZvcihpID0gMDsgaSA8IG07ICsraSkKICAgIHsKICAgICAgICBsbyA9IGFbaV0uZmkgOyBoaSA9IGFbaV0uc2UgOwogICAgICAgIGlmKGxvID09IDEpCiAgICAgICAgewogICAgICAgICAgICBmW2xvXVtoaV0gPSAxOwogICAgICAgIH0KICAgIH0KICAgIGZvcihpID0gMDsgaSA8IG07ICsraSkKICAgIHsKICAgICAgICBsbyA9IGFbaV0uZmkgOyBoaSA9IGFbaV0uc2UgOwogICAgICAgIGlmKGhpID09IG4pCiAgICAgICAgewogICAgICAgICAgICByZXMgKz0gZHAobG8saGkpIDsKICAgICAgICAgICAgcmVzICU9IE1vZCA7CiAgICAgICAgfQogICAgfQogICAgcHJpbnRmKCIlZFxuIixyZXMpIDsKfQo=