#include<bits/stdc++.h>
#define pb push_back 
 #define fo(i,n) for(int i=0;i<n;i++)
#define ll long long 
#define int long long 
#define Mod 10000000000007 
#define maxn 200005
#define MAX 4294967296  // 2^32
const int M=1e9+7;
#define ip pair<int,int>
#define test(t) ll t;cin>>t;while(t--)
  
using namespace std;

long long gcd(int x,int y){
    if(y>x)swap(x,y);
    if(y==0)return x;
    return gcd(y,x%y);
}


void solve(){
int n,k;
int maxi=998244353;
cin>>n>>k;
set<int>s;
while(k--){
    int a,b;
    cin>>a>>b;
    s.insert(a);
    s.insert(b);
}
vector<int>v;
for(auto it=s.begin();it!=s.end();it++)v.push_back(*it);
int y=v.size();
int arr[n+1]={0};
arr[1]=1;
for(int i=1;i<=n;i++){
    for(int j=0;j<y;j++){
        if(i-v[j]>=0)
        arr[i]+=arr[i-v[j]];
    }
}
cout<<arr[n];
}

signed main(){


    // std::string binary = std::bitset<8>(n).to_string();
    ios::sync_with_stdio(0);
    cin.tie(0);
   
solve();


  


}