#include <bits/stdc++.h>
using namespace std;
vector<long long int> dp(1000001, -1);
long long int help(int n, vector<int> arr) {
  if (n <= 0) return 0;
  if (n == 1) return 1;
  if (dp[n] != -1) return dp[n];
  long long int ans = 0;
  for (int i = 0; i < arr.size(); i++) {
    if (arr[i] > n) continue;
    n = n - arr[i];
    ans = (ans + help(n, arr));
    n = n + arr[i];
  }
  dp[n] = ans % 998244353;
  return dp[n];
}
int main() {
  int n, k;
  cin >> n >> k;
  set<int> s;
  while (k--) {
    int a, b;
    cin >> a >> b;
    s.insert(a);
    s.insert(b);
  }
  vector<int> arr;
  for (auto x : s) {
    arr.push_back(x);
  }
  cout << help(n, arr);
}
