#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define endl "\n"
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod=1e7+9;

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int lcm(int a , int b)
{
	return (a*b)/gcd(a,b);
}

int power(int a , int b , int c)
{
    if(a==0) return 0;
    if(b==0) return 1;

    int res=1;
    a=a%c;
    while(b>0)
    {
        if(b&1)
        {
            res=(res*a)%c;
        }
        a=(a*a)%c;
        b>>=1;
    }
    return res;
}

int32_t main()
{

    fast_in_out;

    int t=1;
    //cin>>t;
    while(t--)
    {
		int n ,k,sum = 0;
   		cin>>n>>k;
   		vector<vector<int>>a(k,vector<int>(2));

   		for(int i = 0;i<k ;i++)
   			cin>>a[i][0]>>a[i][1];

   		int dp[n+1]={};
   		int pref[n+1] = {};
   		dp[1] = pref[1] = 1;
   		for(int i = 2;i<= n ;i++)
   		{
   	 		for(int j= 0;j<k ;j++)
   	 		{
   	 			if(i>a[j][0])
   	 			{
   	 				dp[i] += pref[i -a[j][0]];
   	 				if(i > a[j][1])
   	 					dp[i] -= pref[i-a[j][1]-1];
   	 		
   	 				dp[i] = (dp[i] + mod)%mod; 
   	 			}
   	 		}
   	 		pref[i]+= (pref[i-1]+dp[i])%mod;
   		}
  		cout<<dp[n]<<endl;
    }

    return 0;
}
