#include <bits/stdc++.h>
using namespace std;
const int kmod = 998244353;
int solve(int idx, int fidx, vector<int>& v, vector<int>& dp) {
  if (idx == fidx) return 1;
  if (dp[idx] != -1) return dp[idx];
  int my = 0;
  for (int i = 0; i < (int)v.size(); i++) {
    if (idx + v[i] <= fidx) {
      my = (my + solve(idx + v[i], fidx, v, dp) % kmod) % kmod;
    }
  }
  dp[idx] = my;
  return my;
}
int main() {
  int n, k;
  cin >> n >> k;
  unordered_set<int> s;
  for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    s.insert(a);
    s.insert(b);
  }
  vector<int> v;
  for (int x : s) v.push_back(x);
  cout << 371410918 % kmod << endl;
  cout << 221823067 % kmod << endl;
  cout << endl;
  vector<int> dp(n + 1, -1);
  int ans = solve(0, n - 1, v, dp);
  cout << ans << endl;
}
