#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<int, int>;
template <typename T>
inline void _read(T arr, int n) {
  for (int i = 0; i < n; i++) cin >> arr[i];
}
template <typename T>
inline void _write(T arr, int n, bool _space = true, bool _endl = true) {
  if (_space)
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
  else
    for (int i = 0; i < n; i++) cout << arr[i];
  if (_endl) cout << endl;
}
const int MAXN = 200033;
int n, m;
struct Edge {
  int to;
  int id;
  Edge(int to = 0, int id = 0) : to(to), id(id) {}
};
vector<Edge> edges[MAXN];
template <const ll _MOD = (ll)1e18>
inline ll qp(ll x, ll y) {
  ll ret = 1;
  while (y > 0) {
    if (y & 1) ret = ret * x % _MOD;
    x = x * x % _MOD;
    y >>= 1;
  }
  return ret;
}
const int MOD = 998244353;
ll pow2[50];
namespace dij1 {
const ll INF = 1e18;
bool in[MAXN][20];
struct Val {
  int val, k;
  Val(int val = 1e9, int k = 1e9) : val(val), k(k) {}
  bool operator<(const Val &other) const {
    if (k < 40 && other.k < 40) {
      ll val1 = val + pow2[k];
      ll val2 = other.val + pow2[other.k];
      return val1 < val2;
    }
    if (k == other.k) {
      return val < other.val;
    }
    return k < other.k;
  }
  bool operator==(const Val &other) const {
    if (k < 40 && other.k < 40) {
      ll val1 = val + pow2[k];
      ll val2 = other.val + pow2[other.k];
      return val1 == val2;
    }
    return val == other.val && k == other.k;
  }
};
Val dist[MAXN][20];
using PT = pair<Val, pr>;
ll dij(int st) {
  dist[st][0] = Val(0, 0);
  priority_queue<PT, vector<PT>, greater<PT>> Q;
  Q.push({dist[st][0], {st, 0}});
  while (!Q.empty()) {
    auto tp = Q.top().second;
    Q.pop();
    if (in[tp.first][tp.second]) continue;
    in[tp.first][tp.second] = 1;
    for (auto nx : edges[tp.first]) {
      int to = nx.to;
      int ty = nx.id;
      auto now = dist[tp.first][tp.second];
      now.val += 1;
      now.k += ty != tp.second % 2;
      if (now.k < 20 && now.val < dist[to][now.k].val) {
        dist[to][now.k] = now;
        Q.push({dist[to][now.k], {to, now.k}});
      }
    }
  }
  ll mn = INF;
  for (int i = 0; i < 20; i++) {
    if (dist[n][i] == Val()) continue;
    mn = min(mn, (ll)dist[n][i].val + qp(2, i) - 1);
  }
  if (mn == INF) return -1;
  return mn % MOD;
}
};  // namespace dij1
struct Val {
  int val, k;
  Val(int val = 1e9, int k = 1e9) : val(val), k(k) {}
  bool operator<(const Val &other) const {
    if (k == other.k) {
      return val < other.val;
    }
    return k < other.k;
  }
};
Val dist[MAXN][2];
bool in[MAXN][2];
using PT = pair<Val, pr>;
ll dij(int st) {
  dist[st][0] = Val(0, 0);
  priority_queue<PT, vector<PT>, greater<PT>> Q;
  Q.push({dist[st][0], {st, 0}});
  while (!Q.empty()) {
    auto tp = Q.top().second;
    Q.pop();
    if (in[tp.first][tp.second]) continue;
    in[tp.first][tp.second] = true;
    for (auto nx : edges[tp.first]) {
      int to = nx.to;
      int ty = nx.id;
      auto now = dist[tp.first][tp.second];
      now.val += 1;
      now.k += ty ^ tp.second;
      if (now < dist[to][ty]) {
        dist[to][ty] = now;
        if (!in[to][ty]) Q.push({dist[to][ty], {to, ty}});
      }
    }
  }
  if (dist[n][0] < dist[n][1]) {
    return (dist[n][0].val + qp<MOD>(2, dist[n][0].k) - 1 + MOD) % MOD;
  } else {
    return (dist[n][1].val + qp<MOD>(2, dist[n][1].k) - 1 + MOD) % MOD;
  }
}
void __Main__() {
  pow2[0] = 1;
  for (int i = 1; i <= 40; i++) pow2[i] = pow2[i - 1] << 1;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    edges[u].push_back(Edge(v, 0));
    edges[v].push_back(Edge(u, 1));
  }
  ll t = dij1::dij(1);
  if (t == -1) t = dij(1);
  cout << t << endl;
}
signed main() {
  ios ::sync_with_stdio(false);
  cin.tie(nullptr);
  __Main__();
  return 0;
}
