#include <bits/stdc++.h>
using namespace std;
int n, m, a, b;
long long powm[1000007];
long double poww[1000007];
struct wierz {
  vector<int> l, b;
  int byl[35];
};
wierz tab[1000007];
struct CustomCompare {
  bool operator()(const pair<pair<int, int>, int>& a,
                  const pair<pair<int, int>, int>& b) {
    if (a.first.first > 50 || b.first.first > 50) return a > b;
    return ((1ll << a.first.first) - 1 + a.first.second) >
           ((1ll << b.first.first) - 1 + b.first.second);
  }
};
priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>,
               CustomCompare>
    q;
long long dijkstra() {
  q.push(make_pair(make_pair(0, 0), 1));
  while (!q.empty()) {
    int nr = q.top().second;
    auto p = q.top().first;
    q.pop();
    if (nr == n) {
      return ((powm[p.first] + 998244353 - 1) % 998244353 + p.second) %
             998244353;
    }
    if (tab[nr].byl[((p.first) < 30 ? (p.first) : 30 + (p.first) % 2)])
      continue;
    tab[nr].byl[((p.first) < 30 ? (p.first) : 30 + (p.first) % 2)] = 1;
    if (p.first % 2 == 0) {
      for (auto el : tab[nr].l) {
        if (!tab[el].byl[((p.first) < 30 ? (p.first) : 30 + (p.first) % 2)]) {
          q.push(make_pair(make_pair(p.first, p.second + 1), el));
        }
      }
    } else {
      for (auto el : tab[nr].b) {
        if (!tab[el].byl[((p.first) < 30 ? (p.first) : 30 + (p.first) % 2)]) {
          q.push(make_pair(make_pair(p.first, p.second + 1), el));
        }
      }
    }
    if (!tab[nr].byl[((p.first + 1) < 30 ? (p.first + 1)
                                         : 30 + (p.first + 1) % 2)]) {
      p.first++;
      q.push(make_pair(p, nr));
    }
  }
  return -1;
}
int main() {
  powm[0] = 1;
  poww[0] = 1;
  for (int i = 1; i <= 400007; i++) {
    powm[i] = (powm[i - 1] * 2) % 998244353;
    poww[i] = poww[i - 1] * 2;
  }
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    tab[a].l.push_back(b);
    tab[b].b.push_back(a);
  }
  printf("%lld\n", dijkstra());
  return 0;
}
