#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const long long mod = 998244353;
const int bit = 32;
const double pi = acos(-1.0);
struct node {
  long long d;
  int cnt, num, s;
  bool operator<(const node &a) const { return d > a.d; }
};
struct p {
  long long d;
  int cnt, num, s;
  bool operator<(const p &a) const { return cnt > a.cnt; }
};
priority_queue<node> q;
long long d[M][20];
vector<pair<int, int> > v[M];
int n, m;
long long qpow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
void dij() {
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < 19; j++) d[i][j] = inf;
  }
  d[1][0] = 0;
  node st;
  st.d = 0;
  st.cnt = 0;
  st.num = 1;
  st.s = 0;
  q.push(st);
  while (q.size()) {
    node c = q.top();
    q.pop();
    for (auto x : v[c.num]) {
      int y = x.first, ff = x.second;
      if (c.s == ff) {
        if (d[y][c.cnt] > c.d + 1) {
          d[y][c.cnt] = c.d + 1;
          node ss;
          ss.d = d[y][c.cnt];
          ss.cnt = c.cnt;
          ss.num = y;
          ss.s = ff;
          q.push(ss);
        }
      } else {
        if (c.cnt > 17) continue;
        if (d[y][c.cnt + 1] > c.d + pow(2, c.cnt) + 1) {
          d[y][c.cnt + 1] = c.d + pow(2, c.cnt) + 1;
          node ss;
          ss.d = d[y][c.cnt + 1];
          ss.cnt = c.cnt + 1;
          ss.num = y;
          ss.s = ff;
          q.push(ss);
        }
      }
    }
  }
}
pair<int, int> dis[2 * M];
priority_queue<p> q1;
void dij2() {
  for (int i = 0; i <= 2 * n; i++) {
    dis[i].first = inf;
    dis[i].second = inf;
  }
  dis[1].first = 0;
  dis[1].second = 0;
  p st;
  st.d = 0;
  st.cnt = 0;
  st.num = 1;
  st.s = 0;
  q1.push(st);
  while (q1.size()) {
    p c = q1.top();
    q1.pop();
    for (auto x : v[c.num]) {
      int y = x.first, ff = x.second;
      if (c.s == ff) {
        if (ff == 1) y += n;
        if (dis[y].second > c.cnt ||
            (dis[y].second == c.cnt && dis[y].first > c.d + 1)) {
          dis[y].first = c.d + 1;
          dis[y].second = c.cnt;
          p ss;
          ss.d = c.d + 1;
          if (y > n)
            ss.num = y - n;
          else
            ss.num = y;
          ss.cnt = c.cnt;
          ss.s = ff;
          q1.push(ss);
        }
      } else {
        if (ff == 1) y += n;
        if (dis[y].second > c.cnt + 1 ||
            (dis[y].second == c.cnt + 1 && dis[y].first > c.d + 1)) {
          dis[y].first = c.d + 1;
          dis[y].second = c.cnt + 1;
          p ss;
          ss.d = c.d + 1;
          if (y <= n)
            ss.num = y;
          else
            ss.num = y - n;
          ss.cnt = c.cnt + 1;
          ss.s = ff;
          q1.push(ss);
        }
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  int qw = m;
  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(make_pair(y, 0));
    v[y].push_back(make_pair(x, 1));
  }
  dij();
  long long ans = 1ll * inf;
  for (int i = 0; i < 19; i++) {
    ans = min(ans, d[n][i]);
  }
  if (ans == inf) {
    dij2();
    if (dis[n].second < dis[2 * n].second ||
        (dis[n].second == dis[2 * n].second &&
         dis[n].first < dis[2 * n].first)) {
      ans = (qpow(2, dis[n].second) - 1 + dis[n].first) % mod;
    } else
      ans = (qpow(2, dis[n * 2].second) - 1 + dis[n * 2].first) % mod;
  }
  printf("%lld\n", ans % mod);
  return 0;
}
