#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10, pi = 3.1415926535898;
const int mod = 998244353, maxn = 2e5 + 10, maxm = 18;
int T, n, m, k, x, y, z, dp[maxn][20][2];
long long dd[maxn][2];
long long qpow(long long x, int k) {
  long long cnt = 1;
  while (k) {
    if (k & 1) cnt = cnt * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return cnt;
}
vector<int> v[2][maxn];
struct P {
  int x, y, z;
  bool operator<(const P& a) const {
    if (x == a.x) return y < a.y;
    return x < a.x;
  }
};
queue<P> q;
int main(int argc, char const* argv[]) {
  T = 1;
  for (int _ = 1; _ <= T; ++_) {
    long long ans = mod;
    scanf("%d %d", &n, &m);
    for (int i = 1; i < maxn; ++i) {
      for (int j = 0; j < maxm; ++j) dp[i][j][0] = dp[i][j][1] = mod;
    }
    for (int i = 1; i <= m; ++i) {
      scanf("%d %d", &x, &y);
      v[0][x].push_back(y);
      v[1][y].push_back(x);
    }
    dp[1][0][0] = 0;
    q.push({1, 0, 0});
    while (!q.empty()) {
      x = q.front().x;
      y = q.front().y;
      z = q.front().z;
      q.pop();
      for (auto i : v[z][x]) {
        if (dp[x][y][z] + 1 < dp[i][y][z] and
            (y == 0 or dp[x][y][z] + 1 < dp[i][y - 1][z])) {
          dp[i][y][z] = dp[x][y][z] + 1;
          q.push({i, y, z});
        }
      }
      for (auto i : v[z ^ 1][x]) {
        if (y >= maxm) break;
        if (dp[x][y][z] + (1 << y) + 1 < dp[i][y + 1][z ^ 1] and
            (y == 0 or dp[x][y][z] + (1 << y) + 1 < dp[i][y + 1][z ^ 1])) {
          dp[i][y + 1][z ^ 1] = dp[x][y][z] + (1 << y) + 1;
          q.push({i, y + 1, z ^ 1});
        }
      }
    }
    for (int i = 0; i < maxm; ++i) {
      if (dp[n][i][0] < ans) {
        ans = dp[n][i][0];
      } else if (dp[n][i][1] < ans) {
        ans = dp[n][i][1];
      }
    }
    if (ans < mod) {
      printf("%lld\n", ans % mod);
      return 0;
    }
    for (int i = 1; i < maxn; ++i) {
      for (int j = 0; j < 2; ++j) {
        dd[i][j] = 1LL * mod * mod;
      }
    }
    dd[1][0] = 0;
    q.push({1, 0, 0});
    while (!q.empty()) {
      x = q.front().x;
      y = q.front().y;
      z = q.front().z;
      q.pop();
      for (auto i : v[y][x]) {
        if (dd[x][y] + 1 < dd[i][y]) {
          dd[i][y] = dd[x][y] + 1;
          q.push({i, y, 0});
        }
      }
      for (auto i : v[y ^ 1][x]) {
        if (dd[x][y] + mod + 1 < dd[i][y ^ 1]) {
          dd[i][y ^ 1] = dd[x][y] + mod + 1;
          q.push({i, y ^ 1, 0});
        }
      }
    }
    if (dd[n][0] > dd[n][1]) {
      ans = qpow(2, dd[n][1] / mod) + dd[n][1] % mod - 1;
    } else {
      ans = qpow(2, dd[n][0] / mod) + dd[n][0] % mod - 1;
    }
    printf("%lld\n", ans % mod);
  }
  return 0;
}
