#include <bits/stdc++.h>
using namespace std;
 
template<int radix>
#if __cplusplus > 202002L
requires(radix > 1)
#endif
class mod {
    static inline auto normalize(int64_t num) { 
        const auto r = static_cast<int>(num%radix);
        return r > 0 ? r : r < 0 ? radix+r : 0; }
    int value;
public:
    inline mod(int64_t num = 0): value(normalize(num)) {}
    inline mod(const mod &num) : value(num.value) {}
    inline auto operator()() const { return value; }
    inline auto operator-() const { return mod(radix-value); }
    inline auto operator==(const mod &num) const { return value == num.value; }
    inline auto operator!=(const mod &num) const { return value != num.value; }
    inline auto& operator=(const mod &num) { value = num.value; return *this; }
    inline auto& operator+=(const mod &num) { value = normalize(value+num.value); return *this; }
    inline auto& operator-=(const mod &num) { value = normalize(value-num.value); return *this; }
    inline auto& operator*=(const mod &num) { value = normalize(1ll*value*num.value); return *this; }
    inline auto pow(uint64_t x) const { 
        mod z = 1; 
        for (auto y = *this; x > 0; x >>= 1, y *= y)
            if (x&1) z *= y;
        return z; }
    inline mod& operator++() { value = normalize(value+1); return *this; }
    inline mod& operator--() { value = normalize(value-1); return *this; }
    inline mod operator++(int unused) { const auto previous = *this; ++*this; return previous; }
    inline mod operator--(int unused) { const auto previous = *this; --*this; return previous; }
    inline friend auto operator+(mod a, const mod &b) { return a += b; }
    inline friend auto operator-(mod a, const mod &b) { return a -= b; }
    inline friend auto operator*(mod a, const mod &b) { return a *= b; }
    inline friend auto inv(const mod &num) { return num.pow(radix-2); }
    inline auto& operator/=(const mod &num) { value = normalize(1ll*value*inv(num).value); return *this; }
    inline friend auto operator/(mod a, const mod &b) { return a /= b; }
    inline friend auto& operator>>(istream &stream, mod &num) { 
        int64_t v; stream >> v, num.value = normalize(v); return stream; }
    inline friend auto& operator<<(ostream &stream, const mod &num) { return stream << num.value; } };