#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
void dijkstra(int s, vector<vector<pair<int, int> > > &adj,
              vector<pair<int, int> > &dist) {
  dist[s] = make_pair(0, 0);
  priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int> >,
                 greater<pair<pair<int, int>, int> > >
      cola;
  cola.push(make_pair(make_pair(0, 0), 0));
  while (!cola.empty()) {
    pair<pair<int, int>, int> P = cola.top();
    cola.pop();
    int nodo = P.second;
    if (P.first > dist[nodo]) continue;
    for (int i = 0; i < adj[nodo].size(); i++) {
      int nodo2 = adj[nodo][i].first;
      int d = adj[nodo][i].second;
      pair<int, int> D;
      if (d <= -1) {
        D = make_pair(P.first.first + 1, P.first.second);
      } else {
        D = make_pair(P.first.first, P.first.second + d);
      }
      if (D < dist[nodo2]) {
        dist[nodo2] = D;
        cola.push(make_pair(dist[nodo2], nodo2));
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int con = 23;
  vector<vector<pair<int, int> > > adj(con * n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    int orga = a, orgb = b;
    for (int _ = 0; _ < con; _++) {
      if (a != n - 1) adj[a].push_back(make_pair(b, 1));
      swap(a, b);
      if (a != n - 1) a += n;
      if (b != n - 1) b += n;
    }
  }
  for (int i = 0; i + 1 < n; i++) {
    int val = n;
    for (int _ = 0; _ < con - 2; _++) {
      adj[i + val - n].push_back(make_pair(i + val, (1 << _)));
      val += n;
    }
    adj[i + val - n].push_back(make_pair(i + val, -1));
    adj[i + val].push_back(make_pair(i + val - n, -1));
  }
  vector<pair<int, int> > distance(con * n, make_pair(1e9, 1e9));
  dijkstra(0, adj, distance);
  long long d1 = (long long)distance[n - 1].second % mod;
  long long power = (1LL << (long long)(con - 2));
  for (int _ = 0; _ < distance[n - 1].first; _++) {
    d1 += power;
    power <<= 1LL;
    if (power >= mod) power -= mod;
    if (d1 >= mod) d1 -= mod;
  }
  cout << d1 << endl;
  return 0;
}
