#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MOD = 998244353;
const int INF = 1e9;
const int LIM = 24;
vector<int> G[2][MAXN];
int n, m, dis[MAXN];
pair<int, int> d[2][MAXN];
int qpow(int n, int k) {
  int r = 1;
  while (k) {
    if (k & 1) r = 1ll * r * n % MOD;
    n = 1ll * n * n % MOD, k >>= 1;
  }
  return r;
}
pair<int, int> operator+(const pair<int, int>& lhs, int rhs) {
  return pair<int, int>(lhs.first, lhs.second + rhs);
}
pair<int, int> operator*(const pair<int, int>& lhs, int rhs) {
  return pair<int, int>(lhs.first + rhs, lhs.second);
}
void Dijkstra(int k) {
  static bool vis[MAXN];
  struct Node {
    int dis, id;
    Node(int d, int v) : dis(d), id(v) {}
    bool operator<(const Node& rhs) const { return dis > rhs.dis; }
  };
  priority_queue<Node> pq;
  for (int i = 1; i <= n; i++) pq.push(Node(dis[i], i)), vis[i] = 0;
  while (!pq.empty()) {
    int u = pq.top().id;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int v : G[k][u])
      if (dis[u] + 1 < dis[v]) {
        dis[v] = dis[u] + 1;
        if (!vis[v]) pq.push(Node(dis[v], v));
      }
  }
}
void Dijkstra1() {
  static bool vis[2][MAXN];
  struct Node {
    pair<int, int> dis;
    int rev, id;
    Node(pair<int, int> d, int k, int v) : dis(d), rev(k), id(v) {}
    bool operator<(const Node& rhs) const { return dis > rhs.dis; }
  };
  priority_queue<Node> pq;
  for (int i = 1; i <= n; i++) {
    if (dis[i] != INF) {
      d[0][i] = pair<int, int>(0, dis[i]);
      d[1][i] = pair<int, int>(INF, INF);
      pq.push(Node(d[0][i], 0, i));
    } else
      d[0][i] = d[1][i] = pair<int, int>(INF, INF);
    vis[0][i] = vis[1][i] = 0;
  }
  while (!pq.empty()) {
    int k = pq.top().rev, u = pq.top().id;
    pq.pop();
    if (vis[k][u]) continue;
    vis[k][u] = 1;
    for (int v : G[k][u])
      if (d[k][u] + 1 < d[k][v]) {
        d[k][v] = d[k][u] + 1;
        if (!vis[k][v]) pq.push(Node(d[k][v], k, v));
      }
    if (d[k][u] * 1 < d[k ^ 1][u]) {
      d[k ^ 1][u] = d[k][u] * 1;
      if (!vis[k ^ 1][u]) pq.push(Node(d[k ^ 1][u], k ^ 1, u));
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    G[0][u].push_back(v);
    G[1][v].push_back(u);
  }
  for (int i = 1; i <= n; i++) dis[i] = INF;
  dis[1] = 0;
  int ans = INF;
  for (int k = 0; k < LIM; k++) {
    Dijkstra(k & 1);
    ans = min(ans, dis[n]);
    for (int i = 1; i <= n; i++)
      if (dis[i] != INF) dis[i] += 1 << k;
  }
  if (ans != INF)
    printf("%d\n", ans);
  else {
    Dijkstra1();
    pair<int, int> res = min(d[0][n], d[1][n]);
    ans = (res.second + 1ll * qpow(2, LIM) * (qpow(2, res.first) - 1)) % MOD;
    printf("%d\n", ans);
  }
  return 0;
}
