#include <bits/stdc++.h>
using namespace std;
struct type1 {
  int s, x;
} s1;
struct type2 {
  int s, s2, x;
} s2;
int a[400001][3], ls[200001], f[200001][21], g[200001][2][2], n, m, i, j, k, l,
    len, mn, mn2;
long long p[200001], ans;
bool operator<(type1 a, type1 b) { return a.s > b.s; }
bool operator<(type2 a, type2 b) {
  return a.s > b.s || a.s == b.s && a.s2 > b.s2;
}
priority_queue<type1> hp1[21];
priority_queue<type2> hp2;
void New(int x, int y, int z) {
  ++len;
  a[len][0] = y;
  a[len][1] = ls[x];
  ls[x] = len;
  a[len][2] = z;
}
int main() {
  p[0] = 1;
  for (i = 1; i <= 200000; i++) p[i] = p[i - 1] * 2 % 998244353;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) scanf("%d%d", &j, &k), New(j, k, 0), New(k, j, 1);
  memset(f, 127, sizeof(f));
  memset(g, 127, sizeof(g));
  f[1][0] = 0, hp1[0].push({0, 1});
  while (1) {
    mn = 2000000000, mn2 = -1;
    for (i = 0; i <= 20; i++)
      if (!hp1[i].empty()) {
        s1 = hp1[i].top();
        if (s1.s < mn) mn = s1.s, mn2 = i;
      }
    if (mn2 > -1) {
      s1 = hp1[mn2].top(), hp1[mn2].pop();
      if (s1.x == n) break;
      for (i = ls[s1.x]; i; i = a[i][1])
        if (a[i][2] == (mn2 & 1)) {
          if (f[a[i][0]][mn2] > f[s1.x][mn2] + 1)
            f[a[i][0]][mn2] = f[s1.x][mn2] + 1,
            hp1[mn2].push({f[a[i][0]][mn2], a[i][0]});
        } else {
          if (mn2 < 20) {
            if (f[a[i][0]][mn2 + 1] > f[s1.x][mn2] + 1 + p[mn2])
              f[a[i][0]][mn2 + 1] = f[s1.x][mn2] + 1 + p[mn2],
                               hp1[mn2 + 1].push(
                                   {f[a[i][0]][mn2 + 1], a[i][0]});
          } else {
            if (g[a[i][0]][1][0] > 21 ||
                g[a[i][0]][1][0] == 21 && g[a[i][0]][1][1] > f[s1.x][mn2] + 1) {
              g[a[i][0]][1][0] = 21;
              g[a[i][0]][1][1] = f[s1.x][mn2] + 1;
              hp2.push({g[a[i][0]][1][0], g[a[i][0]][1][1], a[i][0]});
            }
          }
        }
    } else {
      s2 = hp2.top(), hp2.pop();
      if (s2.x == n) break;
      for (i = ls[s2.x]; i; i = a[i][1])
        if (a[i][2] == (s2.s & 1)) {
          if (g[a[i][0]][s2.s & 1][0] > g[s2.x][s2.s & 1][0] ||
              g[a[i][0]][s2.s & 1][0] == g[s2.x][s2.s & 1][0] &&
                  g[a[i][0]][s2.s & 1][1] > g[s2.x][s2.s & 1][1] + 1) {
            g[a[i][0]][s2.s & 1][0] = g[s2.x][s2.s & 1][0];
            g[a[i][0]][s2.s & 1][1] = g[s2.x][s2.s & 1][1] + 1;
            hp2.push(
                {g[a[i][0]][s2.s & 1][0], g[a[i][0]][s2.s & 1][1], a[i][0]});
          }
        } else {
          if (g[a[i][0]][!(s2.s & 1)][0] > g[s2.x][s2.s & 1][0] + 1 ||
              g[a[i][0]][!(s2.s & 1)][0] == g[s2.x][s2.s & 1][0] + 1 &&
                  g[a[i][0]][!(s2.s & 1)][1] > g[s2.x][s2.s & 1][1] + 1) {
            g[a[i][0]][!(s2.s & 1)][0] = g[s2.x][s2.s & 1][0] + 1;
            g[a[i][0]][!(s2.s & 1)][1] = g[s2.x][s2.s & 1][1] + 1;
            hp2.push({g[a[i][0]][!(s2.s & 1)][0], g[a[i][0]][!(s2.s & 1)][1],
                      a[i][0]});
          }
        }
    }
  }
  ans = 2000000000;
  for (i = 0; i <= 20; i++) ans = (ans < f[n][i] ? ans : f[n][i]);
  if (ans == 2000000000) {
    if (g[n][0][0] < g[n][1][0])
      l = 0;
    else
      l = 1;
    ans = g[n][l][1];
    for (i = 20; i <= g[n][l][0] - 1; i++) ans = ((ans) + (p[i])) % 998244353;
  }
  printf("%lld\n", ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}
