#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long mod = 998244353;
const int N = 200005;
struct Edge {
  int v, w, next;
} e[N << 1];
int h[N], eid;
void addEdge(int u, int v, int w) {
  e[eid] = {v, w, h[u]};
  h[u] = eid++;
}
int cmp(pair<int, int> t1, pair<int, int> t2) {
  if (t1 == t2) return 0;
  int x1 = t1.first, y1 = t1.second, x2 = t2.first, y2 = t2.second;
  if (x1 <= 20 && x2 <= 20) {
    int s1 = (1 << x1) + y1 - 1, s2 = (1 << x2) + y2 - 1;
    if (s1 == s2) return 0;
    if (s1 > s2) return 1;
    return -1;
  } else {
    if (x1 > x2) return 1;
    if (x1 < x2) return -1;
    if (y1 > y2) return 1;
    return -1;
  }
}
int n, m;
namespace A1 {
struct Node {
  int u, k;
  pair<int, int> d;
  bool operator<(const Node rhs) const {
    if (d.first == rhs.d.first) return d.second > rhs.d.second;
    return d.first > rhs.d.first;
  }
};
pair<int, int> dis[N][2];
int vis[N][2];
pair<int, int> Dijk() {
  for (int i = 1; i <= n; i++) {
    dis[i][0] = dis[i][1] = {INF, INF};
  }
  priority_queue<Node> q;
  dis[1][0] = {0, 0};
  q.push({1, 0, dis[1][0]});
  while (!q.empty()) {
    int u = q.top().u, k = q.top().k;
    int x = q.top().d.first, y = q.top().d.second;
    q.pop();
    if (vis[u][k]) continue;
    vis[u][k] = 1;
    for (int i = h[u]; ~i; i = e[i].next) {
      int v = e[i].v, w = e[i].w;
      pair<int, int> tmp = {x + (w != k), y + 1};
      if (tmp.first < dis[v][w].first ||
          tmp.first == dis[v][w].first && tmp.second < dis[v][w].second) {
        dis[v][w] = tmp;
        q.push({v, w, tmp});
      }
    }
  }
  if (cmp(dis[n][0], dis[n][1]) >= 0)
    return dis[n][1];
  else
    return dis[n][0];
}
}  // namespace A1
namespace A2 {
int vis[N][20];
struct Node {
  int u, x, d;
};
pair<int, int> Dijk() {
  pair<int, int> res = {INF, INF};
  queue<Node> q;
  vis[1][0] = 1;
  q.push({1, 0, 0});
  while (!q.empty()) {
    int u = q.front().u, x = q.front().x, d = q.front().d;
    q.pop();
    if (u == n) {
      pair<int, int> tmp = {x, d};
      if (cmp(res, tmp) == 1) res = tmp;
      continue;
    }
    for (int i = h[u]; ~i; i = e[i].next) {
      int v = e[i].v, w = e[i].w;
      int tx = x + ((x & 1) != w);
      if (tx < 20 && vis[v][tx] == 0) {
        vis[v][tx] = 1;
        q.push({v, tx, d + 1});
      }
    }
  }
  return res;
}
}  // namespace A2
int main() {
  memset(h, -1, sizeof h);
  scanf("%d%d", &n, &m);
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    addEdge(u, v, 0);
    addEdge(v, u, 1);
  }
  pair<int, int> wc = A1::Dijk(), wc2 = A2::Dijk();
  if (cmp(wc, wc2) == 1) wc = wc2;
  long long ans = wc.second, gg = 1;
  for (int i = 0; i < wc.first; i++) {
    ans += gg;
    gg = gg * 2 % mod;
  }
  cout << ans % mod << endl;
  return 0;
}
