//#include "/Users/HIMANSHU PANDEY/Desktop/coding/stdc++.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define ins insert
#define sb substr
#define con continue
#define ub upper_bound
#define lb lower_bound
#define sp fixed<<setprecision
#define bp __builtin_popcountll
#define pll pair<ll,ll>
#define pld pair<ld,ld>
using namespace std;
 
ll power(ll x, ll y);
ll mpower(ll x, ll y, ll p);
ll modInv(ll a, ll m);
ll gcdExtended(ll a, ll b, ll *x, ll *y);
bool isPrime(ll n);
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t,i,j,k,l,h,p,q,r,x,y,z,b,c,d,f,n,m,M=998244353;
    char ch,ch2,ch3;
    string s,s1,s2,s3;
     t=1;
   // cin>>t;
    while(t--)
    {
        vector<ll> v,w;
        unordered_map<ll,ll> N;
        set<ll> S,SS;
		cin>>n>>k;
		for(i=0;i<k;i++)
		{
		    cin>>x>>y;
		    if(N[x]==0)
		    {
		        v.pb(x);
		        N[x]=1;
		    }
		    if(N[y]==0)
		    {
		        v.pb(y);
		        N[y]=1;
		    }
		}
		ll a[n+2]={0};
		for(i=0;i<v.size();i++)
		{
		    for(j=1;v[i]*j<n;j++)
		    {
		        a[1+v[i]*j]=(1+a[1+v[i]*j])%M;
		    }
		}
		ll sum=a[n];
	   	for(i=1;i<n;i++)
		{
		    if(N[n-i]==1)
		    {
		        sum=(sum%M+a[i])%M;
		    }
		}
		cout<<sum%M;
    }
    return 0;
}
 
ll modInv(ll a, ll m)
{
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    ll res = (x%m + m) % m;
    return res;
}
 
ll gcdExtended(ll a, ll b, ll *x, ll *y){
    if (a == 0){
        *x = 0, *y = 1;
        return b;
    }
    ll x1, y1;
    ll gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}
 
ll mpower(ll x, ll y, ll p){
    ll res = 1;
    x = x % p;
    while(y > 0){
        if(y & 1) res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
 
ll power(ll x, ll y){
    ll res = 1;
    while (y > 0){
        if (y & 1) res = res*x;
        y = y>>1;
        x = x*x;
    }
    return res;
}
 
bool isPrime(ll n){
    if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    ll p=sqrt(n);
    for(int i=5;i<=p;i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}