#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;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

You are given a directed graph of n vertices and m edges. Vertices are numbered from 1 to n. There is a token in vertex 1.

The following actions are allowed: 

  * Token movement. To move the token from vertex u to vertex v if there is an edge u → v in the graph. This action takes 1 second. 
  * Graph transposition. To transpose all the edges in the graph: replace each edge u → v by an edge v → u. This action takes increasingly more time: k-th transposition takes 2^{k-1} seconds, i.e. the first transposition takes 1 second, the second one takes 2 seconds, the third one takes 4 seconds, and so on. 



The goal is to move the token from vertex 1 to vertex n in the shortest possible time. Print this time modulo 998 244 353.

Input

The first line of input contains two integers n, m (1 ≤ n, m ≤ 200 000).

The next m lines contain two integers each: u, v (1 ≤ u, v ≤ n; u ≠ v), which represent the edges of the graph. It is guaranteed that all ordered pairs (u, v) are distinct.

It is guaranteed that it is possible to move the token from vertex 1 to vertex n using the actions above.

Output

Print one integer: the minimum required time modulo 998 244 353.

Examples

Input


4 4
1 2
2 3
3 4
4 1


Output


2


Input


4 3
2 1
2 3
4 3


Output


10

Note

The first example can be solved by transposing the graph and moving the token to vertex 4, taking 2 seconds.

The best way to solve the second example is the following: transpose the graph, move the token to vertex 2, transpose the graph again, move the token to vertex 3, transpose the graph once more and move the token to vertex 4.

### Response

```cpp
#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;
}

```