#line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; // https://xn--kst.jp/blog/2019/08/29/cpp-comp/ // debug methods // usage: debug(x,y); // vector 出力できるように修正 template ostream& debug_print(ostream& os, const vector& v) { os << "["; for (size_t i = 0; i < v.size(); ++i) { os << v[i]; if (i < v.size() - 1) os << ", "; } os << "]"; return os; } template ostream& debug_print(ostream& os, const T& var) { os << var; return os; } #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x #define debug_1(x1) { cout << #x1 << ": "; debug_print(cout, x1) << endl; } #define debug_2(x1, x2) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << endl; } #define debug_3(x1, x2, x3) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << endl; } #define debug_4(x1, x2, x3, x4) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << endl; } #define debug_5(x1, x2, x3, x4, x5) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << ", " << #x5 << ": "; debug_print(cout, x5) << endl; } #ifdef LOCAL #define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~))(__VA_ARGS__) #else #define debug(...) #endif using ll = long long; using vl = vector; using Graph = vector>; using P = pair; #define all(v) v.begin(), v.end() template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } #define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i) // https://trap.jp/post/1224/ template constexpr auto min(T... a) { return min(initializer_list>{a...}); } template constexpr auto max(T... a) { return max(initializer_list>{a...}); } template void input(T &...a) { (cin >> ... >> a); } template void input(vector &a) { for(T &x : a) cin >> x; } void print() { cout << '\n'; } template void print(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } void print(const string &s) { cout << s << '\n'; } template struct is_container : std::false_type {}; template struct is_container().begin()), decltype(std::declval().end())>> : std::true_type {}; template typename enable_if::value>::type print(const Container& x) { if (!x.empty()) { auto it = x.begin(); for (; it != prev(x.end()); ++it) { cout << *it << " "; } cout << *it << "\n"; // 最後の要素を出力して改行 } } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1(a) for(ll i = 0; i < a; i++) #define REP2(i, a) for(ll i = 0; i < a; i++) #define REP3(i, a, b) for(ll i = a; i < b; i++) #define REP4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; #line 2 "/home/y_midori/cp/04_yukicoder/457/g.cpp" // #include // using namespace atcoder; // using mint = modint998244353; // https://ei1333.github.io/luzhiled/snippets/math/lagrange-polynomial.htmlから template struct ModInt { int x; ModInt() : x(0) { } ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) { } ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt(t); return (is); } static int get_mod() { return mod; } }; using modint = ModInt<998244353>; template struct Combination { vector _fact, _rfact, _inv; Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) { _fact[0] = _rfact[sz] = _inv[0] = 1; for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i; _rfact[sz] /= _fact[sz]; for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1); for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1]; } inline T fact(int k) const { return _fact[k]; } inline T rfact(int k) const { return _rfact[k]; } inline T inv(int k) const { return _inv[k]; } T P(int n, int r) const { if(r < 0 || n < r) return 0; return fact(n) * rfact(n - r); } T C(int p, int q) const { if(q < 0 || p < q) return 0; return fact(p) * rfact(q) * rfact(p - q); } T H(int n, int r) const { if(n < 0 || r < 0) return (0); return r == 0 ? 1 : C(n + r - 1, r); } }; template T lagrange_polynomial(const vector &y, int64_t t) { int N = y.size() - 1; Combination comb(N); if(t <= N) return y[t]; T ret(0); vector dp(N + 1, 1), pd(N + 1, 1); for(int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i); for(int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i); for(int i = 0; i <= N; i++) { T tmp = y[i] * dp[i] * pd[i] * comb.rfact(i) * comb.rfact(N - i); if((N - i) & 1) ret -= tmp; else ret += tmp; } return ret; } void solve() { LL(n, m); using T = tuple; vector abcd(m); rep(i, m) { LL(a, b, c, d); abcd[i] = T(a, b, c, d); } vector f(4, 1); rep(t, 1, 4) { // if(t > 1) // break; ll cnt = 0; ll lim = 16 * t + 5; for(ll i = -lim; i <= lim; i++) for(ll j = -lim; j <= lim; j++) for(ll k = -lim; k <= lim; k++) { bool flag = true; for(auto [a, b, c, d] : abcd) { d *= t; if(a * i + b * j + c * k + d < 0) { flag = false; break; } } if(flag) { // debug(i, j, k); cnt++; } } f[t] = cnt; } // vector x(4); // rep(i, 4) x[i] = i; // auto g = lagrange_interpolation(x, f); // mint ans = 0; // rep(i, 4) { // ans -= g[i] * (modint(-n).pow(i)); // } ll _n = (998244353 * 2 - n) % 998244353; // _n = (n + 998244353) % 998244353; debug(f, n, _n); modint ans = -lagrange_polynomial(f, _n); // modint ans = lagrange_polynomial(f, n); cout << ans << endl; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << std::setprecision(16); int t = 1; rep(_, t) { solve(); } // int N, T; // cin >> N; // vector A(N + 1); // input(A); // cin >> T; // cout << lagrange_polynomial(A, T) << endl; }