#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  std::cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  std::cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <typename T, typename U>
static inline void amin(T& x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static inline void amax(T& x, U y) {
  if (x < y) x = y;
}
long long max(long long a, long long b) { return (a > b) ? a : b; }
long long min(long long a, long long b) { return (a < b) ? a : b; }
const long long N = 2e5 + 100;
const long long LOGN = 25;
vector<long long> adj[N], rev[N];
long long power(long long x, unsigned long long y, unsigned long long m) {
  if (y == 0) return 1;
  long long p = power(x, y / 2, m) % m;
  p = (p * p) % m;
  return (y % 2 == 0) ? p : (x * p) % m;
}
priority_queue<pair<pair<long long, long long>, long long>,
               vector<pair<pair<long long, long long>, long long>>,
               greater<pair<pair<long long, long long>, long long>>>
    pq;
set<pair<pair<long long, long long>, long long>> s;
long long dp[N][LOGN];
pair<long long, long long> dp2[N][2];
long long solve() {
  long long n, m;
  cin >> n >> m;
  for (long long i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    rev[v].push_back(u);
  }
  s.insert({{0, 0}, 1});
  for (long long i = 2; i < N; i++)
    for (long long j = 0; j < LOGN; j++) dp[i][j] = 1e18;
  long long ans = 1e18;
  while (!s.empty()) {
    auto f = *s.begin();
    s.erase(s.begin());
    long long cost = f.first.first;
    long long trans = f.first.second;
    long long cur = f.second;
    if (dp[cur][trans] < cost) continue;
    if (cur == n) {
      amin(ans, cost + (1ll << trans) - 1);
    }
    long long ntrans = trans + (trans % 2);
    if (ntrans < LOGN)
      for (auto i : adj[cur]) {
        if (dp[i][ntrans] > cost + 1) {
          s.insert({{cost + 1, ntrans}, i});
          dp[i][ntrans] = cost + 1;
        }
      }
    ntrans = trans + (trans % 2 == 0);
    if (ntrans < LOGN)
      for (auto i : rev[cur]) {
        if (dp[i][ntrans] > cost + 1) {
          s.insert({{cost + 1, ntrans}, i});
          dp[i][ntrans] = cost + 1;
        }
      }
  }
  if (ans != 1e18) {
    cout << ans % 998244353 << '\n';
    return 0;
  }
  for (long long i = 2; i < N; i++) dp2[i][0] = dp2[i][1] = {1e18, 1e18};
  dp2[0][0] = {0, 0};
  s.clear();
  s.insert({{0, 0}, 1});
  while (!s.empty()) {
    auto f = *s.begin();
    s.erase(s.begin());
    long long trans = f.first.first;
    long long cost = f.first.second;
    long long cur = f.second;
    if (dp2[cur][trans % 2] > pair<long long, long long>{trans, cost}) continue;
    long long ntrans = trans + (trans % 2);
    for (auto i : adj[cur]) {
      if (dp2[i][ntrans % 2] > pair<long long, long long>{ntrans, cost + 1}) {
        s.insert({{ntrans, cost + 1}, i});
        dp2[i][ntrans % 2] = {ntrans, cost + 1};
      }
    }
    ntrans = trans + (trans % 2 == 0);
    for (auto i : rev[cur]) {
      if (dp2[i][ntrans % 2] > pair<long long, long long>{ntrans, cost + 1}) {
        s.insert({{ntrans, cost + 1}, i});
        dp2[i][ntrans % 2] = {ntrans, cost + 1};
      }
    }
  }
  long long z = 1;
  if (dp2[n][0] < dp2[n][1]) z = 0;
  ans = power(2, dp2[n][z].first, 998244353) - 1 + 998244353 + dp2[n][z].second;
  ans %= 998244353;
  ans += 998244353;
  ans %= 998244353;
  cout << ans << '\n';
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
