// E - Rush Hour 2
#include "bits/stdc++.h"
using namespace std;

#ifndef DEBUG

#define fundri 108
#define debug(...) 1729
#define endl '\n'

#endif

#define int int64_t

typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l = 0, int r = INT_MAX) {return uniform_int_distribution<int>(l, r)(rng);}

bool in_range(int x, int l, int r) {return l <= x && x <= r;}
template<typename H, typename ...T>void inp(H &head) {cin >> head;}
template<typename H, typename ...T>void inp(H &head, T &...tail) {cin >> head;inp(tail...);}
template<typename T>inline istream &operator >>(istream &in, vector<T> &a) {for(T &x : a)in >> x; return in;}
template<typename T, typename U>inline istream &operator >>(istream &in, pair<T, U> &a) {in >> a.first >> a.second; return in;}

// Multi-Dimension Vector
// Usage: vec<n, data-type> dp(dimention-1, dimention-2, ..., dimention-n, default = data-type())
template<int D, typename T> struct vec : public vector<vec<D - 1, T>> {
    static_assert(D >= 1, "Vector dimensions must be greater than zero !!");
    template<typename... Args>
    vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)){}
};

template<typename T> struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val){}};

const int inf = 1e15;
const bool testcases = false;

const bool ready = []() -> bool {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef DHRUV_GHEEWALA
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

    return true;
}();

void solve(int tc);
int32_t main(int32_t argc, char **argv) {
    int TC = 1;
    if(testcases) cin >> TC;

    // Pre-Processing goes here...
    for(int tc = 1; tc <= TC; ++tc) {
        solve(tc);
        fundri;
    }
    exit(0);
}

typedef vector<vector<vector<int>>> graph;
graph adj;
void add_edge(graph &a, int u, int v, int c, int d, bool dir = 0)
{
    a[u].push_back({v, c, d});
    if(!dir) a[v].push_back({u, c, d});
}

void clearAll(int n)
{
    adj.clear();
    adj.resize(n + 1);
}

void solve(int tc) {
    int n, m;
    cin >> n >> m;

    clearAll(n);
    int u, v, c, d;
    for(int i = 0; i < m; i++) {
        cin >> u >> v >> c >> d;
        u--, v--;
        add_edge(adj, u, v, c, d);
    }

    auto calc = [&](int c, int d, int t) {
        return c + d / (t + 1) + t;
    };

    auto get = [&](int c, int d, int t) {
        return calc(c, d, max(t, int(sqrt(d))));
        int l = t, r = inf, ans = calc(c, d, t);
        int m = l;
        while(m < r) {
            if(ans >= calc(c, d, m)) {
                ans = calc(c, d, m);
                m++;
            } else {
                m = r + 1;
            }
        }
        return ans;
    };
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<int> dist(n, inf);
    pq.push({0, 0});

    while(!pq.empty()) {
        const auto fir = pq.top();
        pq.pop();

        debug(fir);
        int t = fir.first;
        int u = fir.second;

        if(dist[u] <= t) continue;
        dist[u] = t;

        for(const auto &vec: adj[u]) {
            int v = vec[0];
            int c = vec[1];
            int d = vec[2];
            int cost = get(c, d, t);
            debug(u, v, c, d, cost);

            if(cost < dist[v])
                pq.push({cost, v});
        }
    }
    cout << (dist[n - 1] == inf ? -1 : dist[n - 1]) << endl;
}
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, k, n) for (int i = k; i < (int)(n); i++)
#define repd(i, n) for (int i = n-1; i >= 0; i--)
#define rrepd(i, k, n) for (int i = n-1; i >= (int)(k); i--)
#define all(x) (x).begin(),(x).end()
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
//V,Pは大文字i,l,bは小文字
using ll = long long;
using Vi = vector<int>;
using VVi = vector<Vi>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using Vb = vector<bool>;
using VVb = vector<Vb>;
using P = pair<int,int>;
using Pl = pair<ll, ll>;
using Vs = vector<string>;
//const ll mod = 1000000007;
const ll inf = 1000000000000000000;//10の18乗
#define yn {puts("Yes");}else{puts("No");}
#define dame { puts("-1"); return 0;}
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    ll n,m;
    cin >> n >> m;
    vector<vector<mint>> dp(50,vector<mint>(10000));
    vector<mint> v(500005);
    v[0]=1;
    v[1]=1;
    dp[0][0]=1;
    rrep(i,1,10005){
        v[i+1]=v[i].x*(i+1);
    }
    //cout << 0 << endl;
    rrep(i,1,21){
        ll x=modpow(2,i-1,mod);
        rep(j,m+1){
            if(dp[i-1][j].x==0) continue;
            for(ll k=0;j+x*k<=m;k+=2){
                //if(dp[i-1][j]==0) 
                if(k>n) break;
                mint plus=v[n].x;
                plus/=v[k].x;
                plus/=v[n-k].x;
                dp[i][j+x*k]+=dp[i-1][j].x*plus.x;
            }
        }
        //cout << 0 << endl;
    }
    /*rep(i,20){rep(j,m+1){
        cout << dp[i][j].x << " ";
    }cout << endl;}*/
    cout << dp[20][m].x << endl;
}