/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
template<typename T>
using P = array<T, 2>;
template<typename U>
using T = array<U, 3>;
template<typename T>
using V = vector<T>;
using VI = vector<int>;
using VL = vector<long long>;
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("avx512f")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")

#define SZ(x) ((long long)(x).size())
#define READ ({long long t;cin >> t;t;})
#define overload4(_1, _2, _3, _4, name, ...) name
#define REP1(n) for(ll i=0;i<n;++i)
#define REP2(i, n) for(ll i=0;i<n;++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 REP(...) overload4(__VA_ARGS__,REP4,REP3,REP2,REP1)(__VA_ARGS__)
#define RREP1(n) for(ll i=n;i--;)
#define RREP2(i, n) for(ll i=n;i--;)
#define RREP3(i, a, b) for(ll i=b;i-->(a);)
#define RREP4(i, a, b, c) for(ll i=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c)
#define RREP(...) overload4(__VA_ARGS__,RREP4,RREP3,RREP2,RREP1)(__VA_ARGS__)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) sort(v.begin(), v.end()), v.erase( unique(v.begin(), v.end()), v.end())
#define EB emplace_back
#define PB push_back
#define fcout cout << fixed << setprecision(12)
#define fcerr cerr << fixed << setprecision(12)
#define print(...) out(cout, __VA_ARGS__)
#define fprint(x) cout << fixed << setprecision(12) << (x) << '\n'
# define BYE(a) do { cout << (a) << endl; return ; } while (false)
#define LB lower_bound
#define UB upper_bound
#define LBI(c, x) distance((c).begin(), lower_bound((c).begin(), (c).end(), (x)))
#define UBI(c, x) distance((c).begin(), upper_bound((c).begin(), (c).end(), (x)))
#define ifn(x) if(!(x))
#define itn int
#define pritn print
#define pirnt print
#define RPE REP
#ifdef DEBUG
#define DBG(args...) ({ string _s = #args; stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(cerr,_it, args); })
#define ERR(args...) ({ string _s = #args; stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(std::cerr,_it, args); })
#else
#define DBG(args...) ({})
#define ERR(args...) ({})
#endif

//@formatter:off
void _err(std::ostream& cerr, istream_iterator<string> it){cerr << endl;}
template<typename T, typename... Args>void _err(std::ostream& cerr, istream_iterator<string> it, T a, Args... args){cerr << (it->empty()||it->back()!=','?(*it):it->substr(0, it->size()-1)) << " = " << a << "  ";_err(cerr, ++it, args...);}
template<class T>int out(ostream& os, const T& t){os << t << '\n';return 0;}
template<class Head, class... Tail>int out(ostream& os, const Head& head, const Tail& ... tail){os << head << ' ';out(os, tail...);return 0;}
template<class T>auto min(T& v){return *min_element(v.begin(), v.end());}
template<class T>auto max(T& v){return *max_element(v.begin(), v.end());}
template<class U = long long, class T> auto sum(T& v){ return accumulate(v.begin(), v.end(), (U) 0); }
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& V){ is >> V.F >> V.S; return is; }
template<typename T> istream& operator>>(istream& is, vector<T>& V){ for(auto&& ele : V)is >> ele; return is; }
template<typename T, size_t N> istream& operator>>(istream& is, array<T, N>& V){ for(auto&& ele : V)is >> ele; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T> V){ os << "["; int cnt = 0; T curr; if(!V.empty()){ for(int i = 0; i < V.size() - 1; ++i){ if(V[i] == curr)cnt++; else cnt = 0; if(cnt == 4)os << "... "; if(cnt < 4) os << i << ":" << V[i] << " "; curr = V[i]; } os << V.size() - 1 << ":" << V.back(); } os << "]\n"; return os; }
template<typename T,size_t N> ostream& operator<<(ostream& os, const array<T,N> V){ os << "["; int cnt = 0; T curr; if(!V.empty()){ for(int i = 0; i < V.size() - 1; ++i){ if(V[i] == curr)cnt++; else cnt = 0; if(cnt == 4)os << "... "; if(cnt < 4) os << i << ":" << V[i] << " "; curr = V[i]; } os << V.size() - 1 << ":" << V.back(); } os << "]\n"; return os; }
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U> P){ os << "("; os << P.first << "," << P.second; os << ")"; return os; }
template<typename T, typename U> ostream& operator<<(ostream& os, const set<T, U> V){ os << "{"; if(!V.empty()){ auto it = V.begin(); for(int i = 0; i < V.size() - 1; ++i){ os << *it << " "; it++; } os << *it; } os << "}\n"; return os; }
template<typename K, typename H, typename P> ostream& operator<<(ostream& os, const unordered_set<K, H, P> V){ os << "{"; if(!V.empty()){ auto it = V.begin(); for(int i = 0; i < V.size() - 1; ++i){ os << *it << " "; it++; } os << *it; } os << "}\n"; return os; }
template<typename K, typename C> ostream& operator<<(ostream& os, const multiset<K, C> V){ os << "{"; if(!V.empty()){ auto it = V.begin(); for(int i = 0; i < V.size() - 1; ++i){ os << *it << " "; it++; } os << *it; } os << "}"; return os; }
template<typename K, typename T, typename C> ostream& operator<<(ostream& os, const map<K, T, C> V){ os << "{"; if(!V.empty()){ auto it = V.begin(); for(int i = 0; i < V.size() - 1; ++i){ os << "("; os << it->first << "," << it->second; os << ") "; it++; } os << "("; os << it->first << "," << it->second; os << ")"; } os << "}\n"; return os; }
template<typename K, typename T, typename C> ostream& operator<<(ostream& os, const unordered_map<K, T, C> V){ os << "{"; if(!V.empty()){ auto it = V.begin(); for(int i = 0; i < V.size() - 1; ++i){ os << "("; os << it->first << "," << it->second; os << ") "; it++; } os << "("; os << it->first << "," << it->second; os << ")"; } os << "}\n"; return os; }
template<typename T> ostream& operator<<(ostream& os, const deque<T> V){ os << "["; if(!V.empty()){ for(int i = 0; i < V.size() - 1; ++i){ os << V[i] << "->"; } if(!V.empty())os << V.back(); } os << "]\n"; return os; };
template<typename T, typename Cont, typename Comp> ostream& operator<<(ostream& os, const priority_queue<T, Cont, Comp> V){ priority_queue<T, Cont, Comp> _V = V; os << "["; if(!_V.empty()){ while(_V.size() > 1){ os << _V.top() << "->"; _V.pop(); } os << _V.top(); } os << "]\n"; return os; };
template<class F> struct y_combinator{ F f; template<class... Args> decltype(auto) operator()(Args&& ... args) const{ return f(*this, std::forward<Args>(args)...); } };
template<class F> y_combinator<decay_t<F>> recursive(F&& f){ return {forward<F>(f)}; }
struct hash_pair{ template<class T1, class T2> size_t operator()(const pair<T1, T2>& p) const{ auto hash1 = hash<T1>{}(p.first); auto hash2 = hash<T2>{}(p.second); return hash1^hash2; } };
template<typename U> auto vec(int n, U v){ return vector<U>(n, v); }
template<typename... Args> auto vec(int n, Args... args){ auto val = vec(forward<Args>(args)...); return vector<decltype(val)>(n, move(val)); }
template<typename T, typename U = less<int>>vector<int> order(vector<T> &a, U comp = less<T>{}){V<int> res(a.size());iota(res.begin(), res.end(), 0);sort(res.begin(), res.end(), [&a,&comp](int l, int r){return comp(a[l], a[r]);});return res;}
const double PI = 2*acos(.0);
const int INF = 0x3f3f3f3f;
template<class T> inline T ceil(T a, T b){return a > 0 ? (a + b - 1)/b : a/b;}
template<class T> inline T floor(T a, T b){return a > 0 ? a/b : (a - b + 1)/b;}
inline long long popcount(ll x){return __builtin_popcountll(x);}
ll pow2(ll a){return 1ll << a;}
ll is_pow2(ll a){return a && !(a&(a-1));}
ll msb(ll a){return a ? 63 - __builtin_clzll(a) : -INF;}
ll lsb(ll a){return a ? INF: __builtin_ctzll(a);}
ll powi(ll a, ll b){ ll res = 1; while(b){ if(b&1) res *= a; a *= a; b >>= 1; } return res; }
ll powp(ll a, ll b, ll p){ ll res = 1; while(b){ if(b&1) (res *= a) %= p; (a *= a) %= p; b >>= 1; } return res; }
template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
template<class T, class U> inline bool chmin(T& a, const U& b){ if(b < a){ a = b; return 1; } return 0; }
vector<int> iota(int N){ vector<int> a(N); iota(a.begin(), a.end(), 0); return a; }
vector<pair<ll, ll>> PF(ll N){ assert(N >= 1); vector<pair<ll, ll>> res; if(~N&1){ res.emplace_back(2, 1); while(~(N /= 2)&1)res.back().second++; } for(ll i = 3; i*i <= N; i += 2) if(N%i == 0){ res.push_back({i, 1}); while((N /= i)%i == 0) res.back().second++; } if(N != 1)res.push_back({N, 1}); return res; }
vector<ll> factors(ll N){ vector<ll> res; ll i = 1; for(; i*i < N; i++){ if(N%i == 0)res.emplace_back(i), res.emplace_back(N/i);} if(i*i == N)res.emplace_back(i); return res; }
//@formatter:on

#ifndef ATCODER_MODINT_HPP
#define ATCODER_MODINT_HPP 1

#ifndef ATCODER_INTERNAL_MATH_HPP
#define ATCODER_INTERNAL_MATH_HPP 1

#include <utility>

namespace atcoder {

namespace internal {

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Fast moduler by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m`
    barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    for (long long a : {2, 7, 61}) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_MATH_HPP

#ifndef ATCODER_INTERNAL_TYPE_TRAITS_HPP
#define ATCODER_INTERNAL_TYPE_TRAITS_HPP 1

#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_TYPE_TRAITS_HPP





#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }
    static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }


  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }
    dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }
  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};

template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_MODINT_HPP

using namespace atcoder;
using mint = modint1000000007;
//using mint = modint998244353;
const int _MX = 3e6;
mint _inv[_MX + 1], _fact[_MX + 1], _inv_fact[_MX + 1];

struct modint_init{
    modint_init(){
        for(int i = 2; i <= _MX; ++i){
            _inv[i] = 1LL*_inv[mint::mod()%i].val()*(mint::mod() - mint::mod()/i)%mint::mod();
        }
        _fact[0] = 1;
        for(unsigned i = 1; i <= _MX; ++i){
            _fact[i] = _fact[i - 1]*i;
        }
        _inv_fact[_MX] = _fact[_MX].inv();
        for(int i = _MX - 1; i >= 0; --i){
            _inv_fact[i] = _inv_fact[i + 1]*(i + 1);
        }
    };
} _modint_init;

mint binom(int n, int r){
    assert(r >= 0);
    assert(n >= r);
    assert(n <= _MX);
    return _fact[n]*_inv_fact[r]*_inv_fact[n - r];
}

mint fact(int n){
    assert(n <= _MX);
    return _fact[n];
}

mint inv(int n){
    assert(n <= _MX);
    return _inv[n];
}

std::ostream& operator<<(std::ostream& os, const mint& x){
    return os << x.val();
}

template<int M, unsigned F>
std::istream& operator>>(std::istream& is, mint& x){
    long long t;
    is >> t;
    x = mint(t);
    return is;
}
void solve(std::istream& cin, std::ostream& cout, std::ostream& cerr){
    ll N;
    cin >> N;
    auto dp = vec(2,2,2,2,mint(0));
    dp[0][0][0][0] = 1;
    RREP(i, 63){
        auto n_dp = vec(2,2,2,2,mint(0));
        int Ni = (N>>i)&1ll;
        DBG(i, Ni);
        REP(j,2)REP(k,2)REP(l,2)REP(m,2)REP(xi,2)REP(yi,2){
            int n_j = 1, n_k = 1, n_l = 1, n_m = 1;
            if(m==0 && !(xi && yi))n_m = 0;
            if(!j && xi>Ni)continue;
            if(!k && yi>Ni)continue;
            if(!l && xi && yi)continue;
            if(!j && xi==Ni)n_j = 0;
            if(!k && yi==Ni)n_k = 0;
            if(!l && !xi && !yi)n_l = 0;
            n_dp[n_j][n_k][n_l][n_m] += dp[j][k][l][m];
        }
        dp = move(n_dp);
        DBG(dp);
    }
    mint ans = 0;
    REP(j,2)REP(k,2)ans += dp[j][k][1][1];
    print(ans/2);
}







#undef int
int main() {
	istream& in(cin);
    ostream& out(cout);
    ostringstream err;
	in.tie(0); ios::sync_with_stdio(0);
    solve(in, out, err);
	return 0;
}