#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int maxn = 2e5 + 10;
int b[maxn];
bool vis[maxn];
int dp[30][maxn];
int n, k;
int main(void) {
  cin >> n >> k;
  int cnt = 0;
  for (int i = 1; i <= k; i++) {
    int x, y;
    cin >> x >> y;
    if (vis[x] == 0) {
      b[++cnt] = x;
      vis[x] = 1;
    }
    if (vis[y] == 0) {
      b[++cnt] = y;
      vis[y] = 1;
    }
  }
  sort(b + 1, b + cnt + 1);
  for (int i = 1; i <= cnt; i++) {
    dp[i][0] = 1;
  }
  for (int j = 1; j < n; j++) {
    dp[0][j] = 0;
  }
  for (int i = 1; i <= cnt; i++) {
    for (int j = 0; j <= n; j++) {
      if (b[i] <= j)
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - b[i]];
      else
        dp[i][j] = dp[i - 1][j];
    }
  }
  cout << dp[cnt][n] << endl;
  return 0;
}
