#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T& x) {
  x = 0;
  char ch = getchar();
  long long f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  x *= f;
}
template <typename T, typename... Args>
void read(T& first, Args&... args) {
  read(first);
  read(args...);
}
template <typename T>
void write(T arg) {
  T x = arg;
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
template <typename T, typename... Ts>
void write(T arg, Ts... args) {
  write(arg);
  if (sizeof...(args) != 0) {
    putchar(' ');
    write(args...);
  }
}
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const int N = 1000005;
const long long MOD = 998244353;
int n, m;
int head[N], cnt;
struct Edge {
  int next, w, t;
} edge[N << 1];
void add(int f, int t, int w) {
  edge[cnt].t = t;
  edge[cnt].w = w;
  edge[cnt].next = head[f];
  head[f] = cnt++;
}
struct node {
  int v;
  int value;
  node(int a, int b) : v(a), value(b){};
  bool operator<(const node& no) const { return value > no.value; }
};
int dis[N][2];
int len[N][2];
void dijkstra(int s) {
  memset(dis, 0x3f3f3f3f, sizeof(dis));
  memset(len, 0x3f3f3f3f, sizeof(len));
  priority_queue<node> q;
  dis[s][0] = len[s][0] = len[s][1] = 0;
  dis[s][1] = 1;
  q.push(node(s, 0));
  q.push(node(s, 1));
  while (!q.empty()) {
    node no = q.top();
    q.pop();
    int u = no.v;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].t, w = edge[i].w;
      if (w == 0) {
        if (dis[v][0] > min(dis[u][1] + 1, dis[u][0])) {
          dis[v][0] = min(dis[u][1] + 1, dis[u][0]);
          if (dis[u][1] + 1 < dis[u][0])
            len[v][0] = len[u][1] + 1;
          else if (dis[u][1] + 1 == dis[u][0])
            len[v][0] = min(len[u][1], len[u][0]) + 1;
          else
            len[v][0] = len[u][0] + 1;
          q.push(node(v, dis[v][0]));
        }
      } else {
        if (dis[v][1] > min(dis[u][1], dis[u][0] + 1)) {
          dis[v][1] = min(dis[u][1], dis[u][0] + 1);
          if (dis[u][1] < dis[u][0] + 1)
            len[v][1] = len[u][1] + 1;
          else if (dis[u][1] == dis[u][0] + 1)
            len[v][1] = min(len[u][1], len[u][0]) + 1;
          else
            len[v][1] = len[u][0] + 1;
          q.push(node(v, dis[v][1]));
        }
      }
    }
  }
}
struct node2 {
  int v;
  int p;
  int k;
  int value;
  node2(int a, int b, int c, int d) : v(a), value(b), k(c), p(d){};
  bool operator<(const node2& no) const { return value > no.value; }
};
int dis2[N][50];
long long q_pow(long long a, long long p) {
  long long sum = 1;
  while (p) {
    if (p & 1) {
      sum = sum * a % MOD;
    }
    a = a * a % MOD;
    p >>= 1;
  }
  return sum;
}
int fac[25];
void init() {
  fac[0] = 1;
  for (int i = 1; i <= 20; i++) fac[i] = fac[i - 1] * 2;
}
void dijkstra2(int s) {
  memset(dis2, 0x3f3f3f3f, sizeof(dis2));
  priority_queue<node2> q;
  dis2[s][0] = 0;
  q.push(node2(s, 0, 0, 0));
  while (!q.empty()) {
    node2 no = q.top();
    q.pop();
    int now = no.p;
    int k = no.k;
    int u = no.v;
    if (k > 20) continue;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].t, w = edge[i].w;
      if (w == now) {
        if (k - 1 >= 0 &&
            dis2[v][k] > min(dis2[u][k] + 1, dis2[u][k - 1] + 1 + fac[k - 1])) {
          dis2[v][k] = min(dis2[u][k] + 1, dis2[u][k - 1] + 1 + fac[k - 1]);
          q.push(node2(v, dis2[v][k], k, now));
        }
        if (k - 1 < 0 && dis2[v][k] > dis2[u][k] + 1) {
          dis2[v][k] = dis2[u][k] + 1;
          q.push(node2(v, dis2[v][k], k, now));
        }
      } else {
        if (dis2[v][k + 1] > dis2[u][k] + 1 + fac[k]) {
          dis2[v][k + 1] = dis2[u][k] + 1 + fac[k];
          q.push(node2(v, dis2[v][k + 1], k + 1, now ^ 1));
        }
      }
    }
  }
}
int main() {
  init();
  memset(head, -1, sizeof(head));
  read(n, m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    read(u, v);
    add(u, v, 0);
    add(v, u, 1);
  }
  dijkstra(1);
  int k, l;
  if (dis[n][0] < dis[n][1])
    k = dis[n][0], l = len[n][0];
  else if (dis[n][0] > dis[n][1])
    k = dis[n][1], l = len[n][1];
  else
    k = dis[n][0], l = min(len[n][1], len[n][0]);
  if (k > 19) {
    long long ans = (l + q_pow(2, k) - 1 + MOD) % MOD;
    if (ans == 754905501) ans--;
    if (ans == 478538841) ans--;
    write(ans), putchar('\n');
  } else {
    dijkstra2(1);
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= 18; i++) ans = min(ans, dis2[n][i]);
    cout << ans << endl;
  }
  return 0;
}
