#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
void *wmem;
char memarr[96000000];
template <class T>
inline void walloc1d(T **arr, int x, void **mem = &wmem) {
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void *)(((char *)(*mem)) + skip[((unsigned long long)(*mem)) & 15]);
  (*arr) = (T *)(*mem);
  (*mem) = ((*arr) + x);
}
template <class T>
inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem) {
  walloc1d(arr, x2 - x1, mem);
  (*arr) -= x1;
}
struct Modint {
  unsigned val;
  Modint() { val = 0; }
  Modint(int a) { val = ord(a); }
  Modint(unsigned a) { val = ord(a); }
  Modint(long long a) { val = ord(a); }
  Modint(unsigned long long a) { val = ord(a); }
  inline unsigned ord(unsigned a) { return a % (998244353U); }
  inline unsigned ord(int a) {
    a %= (int)(998244353U);
    if (a < 0) {
      a += (998244353U);
    }
    return a;
  }
  inline unsigned ord(unsigned long long a) { return a % (998244353U); }
  inline unsigned ord(long long a) {
    a %= (int)(998244353U);
    if (a < 0) {
      a += (998244353U);
    }
    return a;
  }
  inline unsigned get() { return val; }
  inline Modint &operator+=(Modint a) {
    val += a.val;
    if (val >= (998244353U)) {
      val -= (998244353U);
    }
    return *this;
  }
  inline Modint &operator-=(Modint a) {
    if (val < a.val) {
      val = val + (998244353U) - a.val;
    } else {
      val -= a.val;
    }
    return *this;
  }
  inline Modint &operator*=(Modint a) {
    val = ((unsigned long long)val * a.val) % (998244353U);
    return *this;
  }
  inline Modint &operator/=(Modint a) { return *this *= a.inverse(); }
  inline Modint operator+(Modint a) { return Modint(*this) += a; }
  inline Modint operator-(Modint a) { return Modint(*this) -= a; }
  inline Modint operator*(Modint a) { return Modint(*this) *= a; }
  inline Modint operator/(Modint a) { return Modint(*this) /= a; }
  inline Modint operator+(int a) { return Modint(*this) += Modint(a); }
  inline Modint operator-(int a) { return Modint(*this) -= Modint(a); }
  inline Modint operator*(int a) { return Modint(*this) *= Modint(a); }
  inline Modint operator/(int a) { return Modint(*this) /= Modint(a); }
  inline Modint operator+(long long a) { return Modint(*this) += Modint(a); }
  inline Modint operator-(long long a) { return Modint(*this) -= Modint(a); }
  inline Modint operator*(long long a) { return Modint(*this) *= Modint(a); }
  inline Modint operator/(long long a) { return Modint(*this) /= Modint(a); }
  inline Modint operator-(void) {
    Modint res;
    if (val) {
      res.val = (998244353U) - val;
    } else {
      res.val = 0;
    }
    return res;
  }
  inline operator bool(void) { return val != 0; }
  inline operator int(void) { return get(); }
  inline operator long long(void) { return get(); }
  inline Modint inverse() {
    int a = val;
    int b = (998244353U);
    int u = 1;
    int v = 0;
    int t;
    Modint res;
    while (b) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if (u < 0) {
      u += (998244353U);
    }
    res.val = u;
    return res;
  }
  inline Modint pw(unsigned long long b) {
    Modint a(*this);
    Modint res;
    res.val = 1;
    while (b) {
      if (b & 1) {
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  inline bool operator==(int a) { return ord(a) == val; }
  inline bool operator!=(int a) { return ord(a) != val; }
};
inline Modint operator+(int a, Modint b) { return Modint(a) += b; }
inline Modint operator-(int a, Modint b) { return Modint(a) -= b; }
inline Modint operator*(int a, Modint b) { return Modint(a) *= b; }
inline Modint operator/(int a, Modint b) { return Modint(a) /= b; }
inline Modint operator+(long long a, Modint b) { return Modint(a) += b; }
inline Modint operator-(long long a, Modint b) { return Modint(a) -= b; }
inline Modint operator*(long long a, Modint b) { return Modint(a) *= b; }
inline Modint operator/(long long a, Modint b) { return Modint(a) /= b; }
inline int my_getchar() {
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if (s == e && e == 1048576) {
    e = fread(buf, 1, 1048576, stdin);
    s = 0;
  }
  if (s == e) {
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x) {
  int k;
  int m = 0;
  x = 0;
  for (;;) {
    k = my_getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      x = k - '0';
      break;
    }
  }
  for (;;) {
    k = my_getchar();
    if (k < '0' || k > '9') {
      break;
    }
    x = x * 10 + k - '0';
  }
  if (m) {
    x = -x;
  }
}
struct MY_WRITER {
  char buf[1048576];
  int s;
  int e;
  MY_WRITER() {
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER() {
    if (s) {
      fwrite(buf, 1, s, stdout);
    }
  }
};
MY_WRITER MY_WRITER_VAR;
void my_putchar(int a) {
  if (MY_WRITER_VAR.s == MY_WRITER_VAR.e) {
    fwrite(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a) { my_putchar(a); }
inline void wt_L(int x) {
  int s = 0;
  int m = 0;
  char f[10];
  if (x < 0) {
    m = 1;
    x = -x;
  }
  while (x) {
    f[s++] = x % 10;
    x /= 10;
  }
  if (!s) {
    f[s++] = 0;
  }
  if (m) {
    my_putchar('-');
  }
  while (s--) {
    my_putchar(f[s] + '0');
  }
}
inline void wt_L(long long x) {
  int s = 0;
  int m = 0;
  char f[20];
  if (x < 0) {
    m = 1;
    x = -x;
  }
  while (x) {
    f[s++] = x % 10;
    x /= 10;
  }
  if (!s) {
    f[s++] = 0;
  }
  if (m) {
    my_putchar('-');
  }
  while (s--) {
    my_putchar(f[s] + '0');
  }
}
inline void wt_L(Modint x) {
  int i;
  i = (int)x;
  wt_L(i);
}
template <class T, class S>
inline T pow_L(T a, S b) {
  T res = 1;
  res = 1;
  for (;;) {
    if (b & 1) {
      res *= a;
    }
    b >>= 1;
    if (b == 0) {
      break;
    }
    a *= a;
  }
  return res;
}
inline double pow_L(double a, double b) { return pow(a, b); }
template <class S, class T>
inline S chmin(S &a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}
template <class T>
struct DijkstraHeap {
  int *hp;
  int *place;
  int size;
  char *visited;
  T *val;
  void malloc(int N) {
    hp = (int *)std::malloc(N * sizeof(int));
    place = (int *)std::malloc(N * sizeof(int));
    visited = (char *)std::malloc(N * sizeof(char));
    val = (T *)std::malloc(N * sizeof(T));
  }
  void free() {
    std::free(hp);
    std::free(place);
    std::free(visited);
    std::free(val);
  }
  void walloc(int N, void **mem = &wmem) {
    walloc1d(&hp, N, mem);
    walloc1d(&place, N, mem);
    walloc1d(&visited, N, mem);
    walloc1d(&val, N, mem);
  }
  void init(int N) {
    int i;
    size = 0;
    for (i = (0); i < (N); i++) {
      place[i] = -1;
    }
    for (i = (0); i < (N); i++) {
      visited[i] = 0;
    }
  }
  void up(int n) {
    int m;
    while (n) {
      m = (n - 1) / 2;
      if (val[hp[m]] <= val[hp[n]]) {
        break;
      }
      swap(hp[m], hp[n]);
      swap(place[hp[m]], place[hp[n]]);
      n = m;
    }
  }
  void down(int n) {
    int m;
    for (;;) {
      m = 2 * n + 1;
      if (m >= size) {
        break;
      }
      if (m + 1 < size && val[hp[m]] > val[hp[m + 1]]) {
        m++;
      }
      if (val[hp[m]] >= val[hp[n]]) {
        break;
      }
      swap(hp[m], hp[n]);
      swap(place[hp[m]], place[hp[n]]);
      n = m;
    }
  }
  void change(int n, T v) {
    if (visited[n] || (place[n] >= 0 && val[n] <= v)) {
      return;
    }
    val[n] = v;
    if (place[n] == -1) {
      place[n] = size;
      hp[size++] = n;
      up(place[n]);
    } else {
      up(place[n]);
    }
  }
  int pop(void) {
    int res = hp[0];
    place[res] = -1;
    size--;
    if (size) {
      hp[0] = hp[size];
      place[hp[0]] = 0;
      down(0);
    }
    visited[res] = 1;
    return res;
  }
};
struct graph {
  int N;
  int *es;
  int **edge;
  void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem) {
    int i;
    N = N__;
    walloc1d(&es, N, mem);
    walloc1d(&edge, N, mem);
    walloc1d(&edge[0], M, mem);
    for (i = (0); i < (N); i++) {
      es[i] = 0;
    }
    for (i = (0); i < (M); i++) {
      es[A[i]]++;
    }
    for (i = (0); i < (N); i++) {
      walloc1d(&edge[i], es[i], mem);
    }
    for (i = (0); i < (N); i++) {
      es[i] = 0;
    }
    for (i = (0); i < (M); i++) {
      edge[A[i]][es[A[i]]++] = B[i];
    }
  }
};
struct dimcomp2 {
  int B;
  dimcomp2() {}
  dimcomp2(int b) { B = b; }
  dimcomp2(int a, int b) { B = b; }
  inline void set(int b) { B = b; }
  inline void set(int a, int b) { B = b; }
  inline int mask(int a, int b) { return a * B + b; }
  inline int operator()(int a, int b) { return a * B + b; }
  inline void para(int mask, int &a, int &b) {
    a = mask / B;
    b = mask % B;
  }
  inline void operator()(int mask, int &a, int &b) {
    a = mask / B;
    b = mask % B;
  }
};
int N;
int M;
int A[200000];
int B[200000];
graph g[2];
int dist[20][200000];
int q[10000000];
int qs;
int qe;
int main() {
  wmem = memarr;
  int t;
  int i;
  int j;
  int k;
  long long nres;
  long long c;
  Modint res;
  DijkstraHeap<long long> hp;
  rd(N);
  rd(M);
  {
    int Lj4PdHRW;
    for (Lj4PdHRW = (0); Lj4PdHRW < (M); Lj4PdHRW++) {
      rd(A[Lj4PdHRW]);
      A[Lj4PdHRW] += (-1);
      rd(B[Lj4PdHRW]);
      B[Lj4PdHRW] += (-1);
    }
  }
  g[0].setDirectEdge(N, M, A, B);
  g[1].setDirectEdge(N, M, B, A);
  dimcomp2 dm(N);
  for (i = (0); i < (20); i++) {
    for (j = (0); j < (N); j++) {
      dist[i][j] = 1073709056;
    }
  }
  dist[0][0] = 0;
  qs = qe = 5000000;
  q[qe++] = 0;
  while (qe > qs) {
    int t_ynMSdg;
    dm(q[qs++], t, i);
    for (t_ynMSdg = (0); t_ynMSdg < (g[t % 2].es[i]); t_ynMSdg++) {
      auto &k = g[t % 2].edge[i][t_ynMSdg];
      if (dist[t][k] != 1073709056) {
        continue;
      }
      dist[t][k] = dist[t][i] + 1;
      q[qe++] = dm(t, k);
    }
    if (t + 1 < 20 && dist[t + 1][i] == 1073709056) {
      dist[t + 1][i] = dist[t][i];
      q[--qs] = dm(t + 1, i);
    }
  }
  nres = 4611686016279904256LL;
  for (i = (0); i < (20); i++) {
    if (dist[i][N - 1] != 1073709056) {
      chmin(nres, dist[i][N - 1] + (1LL << i) - 1);
    }
  }
  if (nres != 4611686016279904256LL) {
    wt_L(nres);
    wt_L('\n');
    return 0;
  }
  hp.walloc(2 * N);
  hp.init(2 * N);
  hp.change(0, 0LL);
  while (hp.size) {
    int APIVbQlN;
    dm(hp.pop(), t, i);
    c = hp.val[dm(t, i)];
    hp.change(dm((t + 1) % 2, i), c + 10000000000LL);
    for (APIVbQlN = (0); APIVbQlN < (g[t % 2].es[i]); APIVbQlN++) {
      auto &k = g[t % 2].edge[i][APIVbQlN];
      hp.change(dm(t, k), c + 1);
    }
  }
  for (t = (0); t < (2); t++) {
    if (hp.visited[dm(t, N - 1)]) {
      chmin(nres, hp.val[dm(t, N - 1)]);
    }
  }
  res = (pow_L(Modint(2), (nres / 10000000000LL))) + nres % 10000000000LL - 1;
  wt_L(res);
  wt_L('\n');
  return 0;
}
