結果
問題 | No.2156 ぞい文字列 |
ユーザー |
|
提出日時 | 2022-12-09 21:50:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 31,706 bytes |
コンパイル時間 | 1,510 ms |
コンパイル使用メモリ | 132,708 KB |
最終ジャッジ日時 | 2025-02-09 07:52:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <cstddef>#include <limits>#include <tuple>#include <utility>#include <cstdint>namespace bys {using i8 = std::int8_t;using i16 = std::int16_t;using i32 = std::int32_t;using i64 = std::int64_t;using i128 = __int128_t;using u8 = std::uint8_t;using u16 = std::uint16_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using u128 = __uint128_t;using f32 = float;using f64 = double;using f128 = long double;using isize = std::ptrdiff_t;using usize = std::size_t;#define DEFINE_NUM_LITERAL(name, type) \constexpr auto operator"" name(unsigned long long x) { return static_cast<type>(x); }DEFINE_NUM_LITERAL(_i8, std::int8_t);DEFINE_NUM_LITERAL(_i16, std::int16_t);DEFINE_NUM_LITERAL(_i32, std::int32_t);DEFINE_NUM_LITERAL(_i64, std::int64_t);DEFINE_NUM_LITERAL(_i128, __int128_t);DEFINE_NUM_LITERAL(_u8, std::uint8_t);DEFINE_NUM_LITERAL(_u16, std::uint16_t);DEFINE_NUM_LITERAL(_u32, std::uint32_t);DEFINE_NUM_LITERAL(_u64, std::uint64_t);DEFINE_NUM_LITERAL(_u128, __uint128_t);DEFINE_NUM_LITERAL(_z, std::size_t);#undef DEFINE_NUM_LITERAL} // namespace bys#include <array>#include <iostream>#include <type_traits>/*** @file traits.hpp* @brief Types** type_traits拡張*/namespace bys {template <class, class = void> struct has_rshift_from_istream : std::false_type {};template <class T>struct has_rshift_from_istream<T, std::void_t<decltype(std::declval<std::istream&>() >> std::declval<T&>())>> : std::true_type {};template <class T> constexpr bool has_rshift_from_istream_v = has_rshift_from_istream<T>::value;template <class, class = void> struct has_lshift_to_ostream : std::false_type {};template <class T>struct has_lshift_to_ostream<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T&>())>> : std::true_type {};template <class T> constexpr bool has_lshft_to_ostream_v = has_lshift_to_ostream<T>::value;template <class, class = void> struct is_tuple_like : std::false_type {};template <class T> struct is_tuple_like<T, std::void_t<decltype(std::tuple_size<T>())>> : std::true_type {};template <class T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;template <class, class = void> struct is_iterable : std::false_type {};template <class T> struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>()))>> : std::true_type {};template <class T> constexpr bool is_iterable_v = is_iterable<T>::value;template <class T> struct Indexed {static_assert(std::is_integral_v<T>);using resolve_to = T;};using i32_1 = Indexed<i32>;using i64_1 = Indexed<i64>;template <class, class = void> struct is_indexed : std::false_type {};template <class T> struct is_indexed<Indexed<T>> : std::true_type {};template <class T> constexpr bool is_indexed_v = is_indexed<T>::value;template <class T, class = void> struct resolve_type { using type = T; };template <class T> struct resolve_type<T, std::void_t<typename T::resolve_to>> { using type = typename T::resolve_to; };template <class T, std::size_t N> struct resolve_type<std::array<T, N>> {using type = std::array<typename resolve_type<T>::type, N>;};template <class T, class U> struct resolve_type<std::pair<T, U>> {using type = std::pair<typename resolve_type<T>::type, typename resolve_type<U>::type>;};template <class... Args> struct resolve_type<std::tuple<Args...>> {using type = std::tuple<typename resolve_type<Args>::type...>;};template <class T> using resolve_type_t = typename resolve_type<T>::type;} // namespace bys/*** @file constant.hpp* @brief Const*/namespace bys {constexpr i32 MOD7 = 1000000007;constexpr i32 MOD9 = 998244353;constexpr i32 MOD = MOD9;template <class T> constexpr T get_inf();namespace impl {template <class Tp, std::size_t... I> constexpr auto get_inf_tuple(std::index_sequence<I...>) {return Tp{get_inf<typename std::tuple_element_t<I, Tp>>()...};}} // namespace impltemplate <class T> constexpr T get_inf() {if constexpr (std::is_integral_v<T>) {return std::numeric_limits<T>::max() / (T)2;} else if constexpr (std::is_floating_point_v<T>) {return std::numeric_limits<T>::infinity();} else if constexpr (is_tuple_like_v<T>) {return impl::get_inf_tuple<T>(std::make_index_sequence<std::tuple_size_v<T>>());} else {static_assert([]() { return false; }, "Type Error");}}template <class T> constexpr bool is_inf(T x) { return x == get_inf<T>(); }template <class T> constexpr auto inf_v = get_inf<T>();constexpr auto INF = inf_v<i32>;constexpr auto LINF = inf_v<i64>;} // namespace bys#include <vector>#include <algorithm>#include <cassert>#include <string>/*** @file bit.hpp* @brief Bit* @note c++20で<bit>が追加される*/namespace bys {/*** @brief bit幅** bit_width(x) - 1 < log2(x) <= bit_width(x)*/template <class T> constexpr i32 bit_width(T x) {i32 bits = 0;x = (x < 0) ? (-x) : x;for (; x != 0; bits++) x >>= 1;return bits;}//! @brief 2冪に切り下げtemplate <class T> constexpr T bit_floor(T x) {assert(x >= 0);return x == 0 ? 0 : T(1) << (bit_width(x) - 1);}//! @brief 2冪に切り上げtemplate <class T> constexpr T bit_ceil(T x) {assert(x >= 0);return x == 0 ? 1 : T(1) << bit_width(x - 1);}//! @brief 2進文字列に変換template <class T> std::string bin(T n) {assert(n >= 0);if (n == 0) return "0";std::string res;while (n > 0) {res.push_back(n & 1 ? '1' : '0');n >>= 1;}std::reverse(res.begin(), res.end());return res;}//! @brief d bit目が立っているかtemplate <class T> constexpr bool pop(T s, i32 d) { return s & (T(1) << d); }} // namespace bys/*** @file numeric.hpp* @brief Numeric** 数値計算詰め合わせ*/namespace bys {//! @brief 整数の累乗constexpr i64 int_pow(i32 a, i32 b) {i64 res = 1;for (i32 i = 0; i < b; ++i) res *= a;return res;}/*** @brief 繰り返し二乗法** O(log q)*/constexpr i64 mod_pow(i64 p, i64 q, i64 mod) {if (mod == 1) return 0_i64;i128 res = 1;i128 b = p % mod;while (q) {if (q & 1) res = res * b % mod;b = b * b % mod;q >>= 1;}return (i64)res;}//! @brief ceil(x / y)template <class T> constexpr T ceildiv(T x, T y) {if ((x < T(0)) ^ (y < T(0))) {return x / y;} else {return (x + y + (x < T(0) ? 1 : -1)) / y;}}//! @brief floor(x / y)template <class T> constexpr T floordiv(T x, T y) {if ((x < T(0)) ^ (y < T(0))) {return (x - y + (x < T(0) ? 1 : -1)) / y;} else {return x / y;}}/*** @brief Python::divmod** See: https://docs.python.org/ja/3/library/functions.html#divmod*/template <class T> constexpr std::pair<T, T> divmod(T x, T y) {auto q = floordiv(x, y);return {q, x - q * y};}/*** @brief Python::%** See: https://docs.python.org/ja/3/reference/expressions.html#index-68*/template <class T, class S> constexpr T floormod(T x, S mod) {x %= mod;if (x < 0) x += mod;return x;}namespace impl {constexpr i64 isqrt_aux(i64 c, i64 n) {if (c == 0) return 1;i64 k = (c - 1) / 2;i64 a = isqrt_aux(c / 2, n >> (2 * k + 2));return (a << k) + (n >> (k + 2)) / a;}} // namespace impl/*** @brief Python::math.isqrt** floor(sqrt(n))* See: https://docs.python.org/ja/3/library/math.html#math.isqrt*/template <class T> constexpr T isqrt(T n) {assert(n >= 0);if (n == T(0)) return T(0);i64 a = impl::isqrt_aux((bit_width(n) - 1) / 2, n);return n < a * a ? a - 1 : a;}/*** @brief Nim::math::almostEqual** See: https://nim-lang.org/docs/math.html#almostEqual,T,T,Natural*/template <class T, typename std::enable_if_t<std::is_floating_point_v<T>, std::nullptr_t> = nullptr>constexpr bool isclose(T x, T y, T coef = 4.0) {if (x == y) return true;auto diff = std::abs(x - y);return diff <= std::numeric_limits<T>::epsilon() * std::abs(x + y) * coef || diff < std::numeric_limits<T>::min();}constexpr std::pair<i64, i64> inv_gcd(i64 a, i64 b) {a = floormod(a, b);if (a == 0) return {b, 0};i64 s = b, t = a;i64 m0 = 0, m1 = 1;while (t) {i64 u = s / t;s -= t * u;m0 -= m1 * u;auto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}if (m0 < 0) m0 += b / s;return {s, m0};}//! @brief Count multipules of k in the [left, right)template <class T> constexpr T range_multiples(T left, T right, T k) { return (right - 1) / k - (left - 1) / k; }template <class T> constexpr T multiple_floor(T x, T k) { return x / k * k; }template <class T> constexpr T multiple_ceil(T x, T k) { return ceildiv(x, k) * k; }} // namespace bys/*** @file prime.hpp* @brief Prime*/namespace bys {/*** @brief 素因数分解** 試し割り法* O(√n)*/template <typename T> std::vector<T> prime_factorize(T n) {std::vector<T> res;while (n % 2 == 0) {res.push_back(2);n /= 2;}T f = 3;while (f * f <= n) {if (n % f == 0) {res.push_back(f);n /= f;} else {f += 2;}}if (n != 1) res.push_back(n);return res;}namespace impl {template <std::size_t N> constexpr bool miller_rabin(i64 n, std::array<i64, N> bases) {auto d = n - 1;while (d % 2 == 0) d >>= 1;for (auto b : bases) {if (n <= b) break;auto t = d;i128 y = mod_pow(b, 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;}} // namespace impl/*** @brief Miller-Rabin素数判定** 2^64以下なら正確に判定できる* See: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test* See: https://miller-rabin.appspot.com** @note c++20でconstexpr関数内でもvectorが使えるように*/constexpr bool is_prime(i64 n) {if (not(n & 1)) return n == 2;if (n <= 1) return false;if (n <= std::numeric_limits<i32>::max()) {std::array<i64, 3> bases = {2, 7, 61};return impl::miller_rabin(n, bases);} else {std::array<i64, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};return impl::miller_rabin(n, bases);}}} // namespace bys/*** @file modint.hpp* @brief Modint*/namespace bys {/*** @brief ModInt** ac-libraryのmodintをconstexpr化したもの* See: https://atcoder.github.io/ac-library/document_ja/modint.html** @tparam Modulo 法*/template <u32 Modulo> class ModInt {u32 _v;public:static constexpr u32 mod = Modulo;// static_assert(is_prime(mod), "Modulo need to be prime.");static_assert(mod < (std::numeric_limits<u32>::max() >> 1), "Modulo need to be <2^31.");constexpr ModInt() noexcept : _v(0) {}template <class T, std::enable_if_t<std::is_unsigned_v<T>, std::nullptr_t> = nullptr>constexpr ModInt(T v) noexcept : _v(v % mod) {}template <class T, std::enable_if_t<std::is_signed_v<T>, std::nullptr_t> = nullptr>constexpr ModInt(T v) noexcept : _v(floormod(v, mod)) {}constexpr ModInt pow(i64 n) const noexcept {ModInt res = 1, p = *this;while (n) {if (n & 1) res *= p;p *= p;n >>= 1;}return res;}constexpr ModInt inv() const noexcept {if constexpr (is_prime(mod)) {return pow(mod - 2);} else {return inv_gcd(_v, mod).second;}}constexpr ModInt& operator+=(const ModInt rhs) noexcept {_v += rhs._v;if (_v >= mod) _v -= mod;return *this;}constexpr ModInt& operator-=(const ModInt rhs) noexcept {if (rhs._v > _v) _v += mod;_v -= rhs._v;return *this;}constexpr ModInt& operator*=(const ModInt rhs) noexcept {u64 z = _v;z *= rhs._v;_v = (u32)(z % mod);return *this;}constexpr ModInt& operator/=(const ModInt rhs) noexcept { return *this = *this * rhs.inv(); }constexpr ModInt operator+() const noexcept { return *this; }constexpr ModInt operator-() const noexcept { return ModInt() - *this; }constexpr ModInt& operator++() noexcept {_v++;if (_v == mod) _v = 0;return *this;}constexpr ModInt& operator--() noexcept {if (_v == 0) _v = mod;--_v;return *this;}constexpr ModInt operator++(i32) noexcept {ModInt res = *this;++*this;return res;}constexpr ModInt operator--(i32) noexcept {ModInt res = *this;--*this;return res;}friend constexpr ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }friend constexpr ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }friend constexpr ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }friend constexpr ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }friend constexpr bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs._v == rhs._v; }friend constexpr bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs._v != rhs._v; }friend std::istream& operator>>(std::istream& is, ModInt& m) noexcept { return is >> m._v; }friend std::ostream& operator<<(std::ostream& os, const ModInt& m) noexcept { return os << m._v; }};using Mint = ModInt<MOD>;using Mint7 = ModInt<MOD7>;using Mint9 = ModInt<MOD9>;} // namespace bys#include <cmath>#include <numeric>/*** @file matrix.hpp* @brief Matrix* @todo geoとの連携*/namespace bys {//! @brief 行列template <class T> struct Matrix {std::vector<std::vector<T>> mat;Matrix(i32 i, i32 j) : mat(i, std::vector<T>(j)), r(i), c(j) {}Matrix(const std::vector<std::vector<T>>& v) : mat(v), r(v.size()), c(v[0].size()) {}std::vector<T>& operator[](i32 k) { return mat[k]; }i32 row() const { return r; }i32 col() const { return c; }std::pair<i32, i32> shape() const { return {r, c}; }Matrix operator+(const Matrix<T>& rh) const {assert(shape() == rh.shape());Matrix<T> res(r, c);for (i32 i = 0; i < r; ++i) {for (i32 j = 0; j < c; ++j) {res[i][j] = mat[i][j] + rh.mat[i][j];}}return res;}Matrix operator-(const Matrix<T>& rh) const {assert(shape() == rh.shape());Matrix<T> res(r, c);for (i32 i = 0; i < r; ++i) {for (i32 j = 0; j < c; ++j) {res[i][j] = mat[i][j] - rh.mat[i][j];}}return res;}Matrix operator*(const T rh) const {Matrix<T> res(r, c);for (i32 i = 0; i < r; ++i) {for (i32 j = 0; j < c; ++j) {res[i][j] = mat[i][j] * rh;}}return res;}Matrix operator/(const T rh) const {Matrix<T> res(r, c);for (i32 i = 0; i < r; ++i) {for (i32 j = 0; j < c; ++j) {res[i][j] = mat[i][j] / rh;}}return res;}Matrix operator*(const Matrix<T>& rh) const {assert(col() == rh.row());i32 d = rh.col();Matrix<T> res(r, d);for (i32 i = 0; i < r; ++i) {for (i32 j = 0; j < d; ++j) {for (i32 k = 0; k < c; ++k) {res.mat[i][j] += mat[i][k] * rh.mat[k][j];}}}return res;}std::vector<T> operator*(const std::vector<T>& rh) const {i32 n = rh.size();assert(col() == n);std::vector<T> res(r);for (i32 i = 0; i < r; ++i) {res[i] = std::inner_product(mat[i].begin(), mat[i].end(), rh.begin(), (T)0);}return res;}Matrix rotate90() const {Matrix<T> res(c, r);for (i32 i = 0; i < r; ++i) {for (i32 j = 0; j < c; ++j) {res.mat[j][r - i - 1] = mat[i][j];}}return res;}auto pow(i64 p) const {assert(r == c);auto res = Matrix<T>::ident(r);auto base = *this;for (; p > 0; p >>= 1, base = base * base) {if (p & 1) res = res * base;}return res;}static Matrix<T> ident(i32 n) {Matrix res(n, n);for (i32 i = 0; i < n; ++i) res.mat[i][i] = T(1);return res;}static Matrix<double> rotate(double theta) {Matrix<double> res(2, 2);res[0][0] = std::cos(theta);res[0][1] = -std::sin(theta);res[1][0] = std::sin(theta);res[1][1] = std::cos(theta);return res;}private:i32 r, c;};} // namespace bys/*** @file template.hpp* @author bayashi_cl** C++ library for competitive programming by bayashi_cl* Repository: https://github.com/bayashi-cl/byslib* Document : https://bayashi-cl.github.io/byslib/*/#ifndef LOCAL#define NDEBUG#endif/*** @file change.hpp* @brief chmin/chmax*/namespace bys {/*** @brief 最大値で更新* @return true 更新されたとき*/template <class T> constexpr bool chmax(T& a, T const& b) { return a < b ? a = b, true : false; }/*** @brief 最小値で更新* @return true 更新されたとき*/template <class T> constexpr bool chmin(T& a, T const& b) { return a > b ? a = b, true : false; }} // namespace bys#include <iterator>namespace bys {template <class Iterator> class SubRange {public:using iterator = Iterator;using reverse_iterator = std::reverse_iterator<iterator>;using value_type = typename iterator::value_type;using reference = value_type&;using const_reference = const value_type&;SubRange() = default;SubRange(const SubRange& s) : _begin(s._begin), _end(s._end) {}SubRange(const iterator& begin, const iterator& end) : _begin(begin), _end(end) {}iterator begin() const noexcept { return _begin; }iterator end() const noexcept { return _end; }reverse_iterator rbegin() const noexcept { return reverse_iterator{_end}; }reverse_iterator rend() const { return reverse_iterator{_begin}; }reference operator[](std::size_t i) noexcept { return *(_begin + i); }const_reference operator[](std::size_t i) const noexcept { return *(_begin + i); }auto size() const noexcept { return _end - _begin; }bool empty() const noexcept { return _begin == _end; }auto to_vec() const { return std::vector(_begin, _end); }private:iterator _begin, _end;};template <class Iterable> auto reversed(Iterable&& iter) {static_assert(is_iterable_v<Iterable>, "iter is not iterable");return SubRange(std::rbegin(std::forward<Iterable>(iter)), std::rend(std::forward<Iterable>(iter)));}} // namespace bys/*** @file enumerate.hpp* @brief Python::enumerate** Python再現シリーズ enumerate編* See: https://docs.python.org/ja/3/library/functions.html#enumerate*/namespace bys {template <class Iterator> struct EnumerateIterator {public:using difference_type = typename Iterator::difference_type;using value_type = std::tuple<i32, typename Iterator::value_type>;// using pointer = value_type*;using reference = value_type&;using iterator_category = std::forward_iterator_tag;EnumerateIterator(const Iterator& iterator, i32 idx) : index(idx), value(iterator) {}auto& operator++() {++value;++index;return *this;}bool operator!=(const EnumerateIterator& other) const { return value != other.value; }auto operator*() const { return std::tie(index, *value); }private:i32 index;Iterator value;};/*** @brief enumerate** @param iterable 対象* @param start indexの初期値*/template <class Iterable> auto enumerate(Iterable& iterable, i32 start = 0) {using iterator_t = EnumerateIterator<typename Iterable::iterator>;i32 end = static_cast<i32>(iterable.size()) + start;return SubRange(iterator_t(std::begin(iterable), start), iterator_t(std::end(iterable), end));}/*** @brief const enumerate** @param iterable 対象* @param start indexの初期値*/template <class Iterable> auto cenumerate(Iterable& iterable, i32 start = 0) {using iterator_t = EnumerateIterator<typename Iterable::const_iterator>;i32 end = static_cast<i32>(iterable.size()) + start;return SubRange(iterator_t(std::cbegin(iterable), start), iterator_t(std::cend(iterable), end));}} // namespace bys/*** @file irange.hpp* @brief Python::range** Python再現シリーズ range編* See: https://docs.python.org/ja/3/library/stdtypes.html#range*/namespace bys {template <class T> class IntegerIncrementIterator {public:using difference_type = std::ptrdiff_t;using value_type = T;using reference = T;using pointer = T*;using iterator_category = std::bidirectional_iterator_tag;explicit IntegerIncrementIterator(T x) : value(x) {}reference operator*() noexcept { return value; }const reference operator*() const noexcept { return value; }auto operator++() noexcept {++value;return *this;}auto operator++(int) noexcept {auto temp = *this;++*this;return temp;}auto operator--() noexcept {--value;return *this;}auto operator--(int) {auto temp = *this;--*this;return temp;}bool operator!=(IntegerIncrementIterator const& other) const { return value != other.value; }bool operator==(IntegerIncrementIterator const& other) const { return value == other.value; }private:value_type value;};template <class T> class IntegerStepIterator {public:using difference_type = std::ptrdiff_t;using value_type = T;using reference = T;using pointer = T*;using iterator_category = std::bidirectional_iterator_tag;explicit IntegerStepIterator(T f, T x, T s) : start(f), value(x), step(s) {}reference operator*() noexcept { return start + value * step; }const reference operator*() const noexcept { return start + value * step; }auto operator++() {++value;return *this;}auto operator++(int) {auto temp = *this;++*this;return temp;}auto operator--() {--value;return *this;}auto operator--(int) {auto temp = *this;--*this;return temp;}bool operator!=(IntegerStepIterator const& other) const { return value != other.value; }bool operator==(IntegerStepIterator const& other) const { return value == other.value; }private:value_type start, value, step;};template <class T> SubRange<IntegerIncrementIterator<T>> irange(T stop) {static_assert(std::is_integral_v<T>, "T is not integer.");using iterator_t = IntegerIncrementIterator<T>;if (stop < static_cast<T>(0)) stop = static_cast<T>(0);return SubRange(iterator_t(static_cast<T>(0)), iterator_t(stop));}template <class T> SubRange<IntegerIncrementIterator<T>> irange(T start, T stop) {static_assert(std::is_integral_v<T>, "T is not integer.");using iterator_t = IntegerIncrementIterator<T>;if (stop < start) stop = start;return SubRange(iterator_t(start), iterator_t(stop));}template <class T> SubRange<IntegerStepIterator<T>> irange(T start, T stop, T step) {static_assert(std::is_integral_v<T>, "T is not integer.");using iterator_t = IntegerStepIterator<T>;assert(step != 0);auto w = step >= 0 ? stop - start : start - stop;auto s = step >= 0 ? step : -step;if (w < 0) w = 0;return SubRange(iterator_t(start, static_cast<T>(0), step), iterator_t(start, (w + s - 1) / s, step));}} // namespace bysusing std::literals::string_literals::operator""s;/*** @file macro.hpp* @brief Macro*/// clang-format off#define CONCAT_IMPL(a, b) a##b#define CONCAT(a, b) CONCAT_IMPL(a, b)//! @brief [[maybe_unused]]な変数を生成。#define UV [[maybe_unused]] auto CONCAT(unused_val_, __LINE__)#define RE std::runtime_error("file: "s + __FILE__ + ", line: "s + std::to_string(__LINE__) + ", func: "s + __func__)#ifdef LOCAL#define DEBUGBLOCK(block) block#else#define DEBUGBLOCK(block)#endif// clang-format on#include <iomanip>/*** @file printer.hpp* @brief Output*/namespace bys {class Printer {std::ostream& _os;// sep1 "\n" : iterable<iterable>// sep2 " " or "\n": iterable, args// sep3 " " : tuple_likestd::string sep1 = "\n", sep2 = " ", sep3 = " ", end = "\n";template <std::size_t I, class T> void print_tuple_element(T&& elem) {if constexpr (I != 0) cat(sep3);cat(std::forward<T>(elem));}template <class Tp, std::size_t... I> void print_tuple(Tp&& tp, std::index_sequence<I...>) {(print_tuple_element<I>(std::forward<std::tuple_element_t<I, std::decay_t<Tp>>>(std::get<I>(tp))), ...);}public:Printer() = delete;Printer(std::ostream& os) : _os(os) { _os << std::fixed << std::setprecision(11) << std::boolalpha; }~Printer() { _os << std::flush; }template <class T> void cat(T&& v) {if constexpr (has_lshft_to_ostream_v<std::decay_t<T>>) {_os << v;} else if constexpr (is_iterable_v<std::decay_t<T>>) {std::string sep;if constexpr (is_iterable_v<typename std::decay_t<T>::value_type>) {sep = sep1;} else {sep = sep2;}bool top = true;for (auto&& vi : v) {top ? (void)(top = false) : cat(sep);cat(vi);}} else if constexpr (is_tuple_like_v<std::decay_t<T>>) {print_tuple(std::forward<T>(v), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());} else {static_assert([] { return false; }(), "type error");}}void print() { cat(end); }template <class T> void print(T&& v) {cat(std::forward<T>(v));cat(end);}template <class T, class... Ts> void print(T&& top, Ts&&... args) {cat(std::forward<T>(top));cat(sep2);print(std::forward<Ts>(args)...);}template <class... Ts> void operator()(Ts&&... args) { print(std::forward<Ts>(args)...); }void flush() { _os << std::flush; }template <class... Ts> void send(Ts&&... args) {print(std::forward<Ts>(args)...);flush();}Printer set_sep(const std::string& sep_1, const std::string& sep_2, const std::string& sep_3) {sep1 = sep_1;sep2 = sep_2;sep3 = sep_3;return *this;}Printer set_sep(const std::string& sep_2) {sep2 = sep_2;return *this;}Printer set_end(const std::string& _end) {end = _end;return *this;}};} // namespace bys/*** @file scanner.hpp* @brief Input*/namespace bys {class Scanner {std::istream& _is;template <class T, std::size_t... I> auto read_tuple(std::index_sequence<I...>) {return resolve_type_t<T>{read<typename std::tuple_element_t<I, T>>()...};}public:Scanner() = delete;Scanner(std::istream& is) : _is(is) { _is.tie(nullptr); }template <class T> auto read() {if constexpr (has_rshift_from_istream_v<T>) {T res;_is >> res;return res;} else if constexpr (is_tuple_like_v<T>) {return read_tuple<T>(std::make_index_sequence<std::tuple_size_v<T>>());} else if constexpr (is_indexed_v<T>) {typename T::resolve_to n;_is >> n;return --n;} else {static_assert([] { return false; }(), "TypeError");}}template <class... Ts, std::enable_if_t<(sizeof...(Ts) >= 2), std::nullptr_t> = nullptr> auto read() {return std::tuple{read<Ts>()...};}template <class T, std::size_t N> auto read() {std::array<resolve_type_t<T>, N> res;for (auto&& e : res) e = read<T>();return res;}template <class T> auto readvec(i32 n) {std::vector<resolve_type_t<T>> res(n);for (auto&& e : res) e = read<T>();return res;}template <class T> auto readvec(i32 n, i32 m) {std::vector<std::vector<resolve_type_t<T>>> res(n);for (auto&& e : res) e = readvec<T>(m);return res;}};} // namespace bys/*** @file io.hpp* @brief I/O*/namespace bys {template <class... Args> std::string debugfmt(i32 line, Args&&... args) {std::stringstream ss;Printer printer(ss);ss << "📌 line" << std::setw(4) << line << ": ";printer.set_sep("\n ", " ", " ");printer.print(std::forward<Args>(args)...);return ss.str();}Printer print(std::cout), debug(std::cerr);Scanner scanner(std::cin);#ifdef LOCAL//! @brief デバッグ用出力 ジャッジ上では何もしない。#define DEBUG(...) \{ \debug.cat(debugfmt(__LINE__, __VA_ARGS__)); \debug.flush(); \}#else#define DEBUG(...)#endif#define DEBUGCASE(casenum, ...) \if (TESTCASE == casenum) DEBUG(__VA_ARGS__)//! @brief printしてreturnする。#define EXIT(...) \{ \print(__VA_ARGS__); \return; \}} // namespace bys#include <unistd.h>/*** @file solver.hpp* @brief Solver*/namespace bys {struct Solver {static inline i32 TESTCASE = 1;static void solve();static i32 main(i32 t = 1) {std::ios::sync_with_stdio(false);for (; TESTCASE <= t; ++TESTCASE) solve();#ifdef LOCALif (not std::cin.good()) std::cerr << "🟡 Input failed." << std::endl;if (not isatty(STDIN_FILENO) and not std::ws(std::cin).eof()) std::cerr << "🟡 Unused input." << std::endl;#endifreturn 0;}};} // namespace bys/*** @file stdlib.hpp* @brief STL Template*/#include <bitset>#include <complex>#include <functional>#include <map>#include <queue>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>namespace bys {using std::array, std::vector, std::string, std::set, std::map, std::pair;using std::cin, std::cout, std::endl;using std::min, std::max, std::sort, std::reverse, std::abs;// aliasusing Pa = std::pair<i32, i32>;using Pa64 = std::pair<i64, i64>;template <class T> using uset = std::unordered_set<T>;template <class S, class T> using umap = std::unordered_map<S, T>;} // namespace bysnamespace bys {void Solver::solve() {auto n = scanner.read<i64>();Matrix<Mint> mat = vector<vector<Mint>>({{1, 1}, {1, 0}});vector<Mint> e = {1, 0};auto ans = mat.pow(n - 1) * e;print(ans[0] + ans[1] - 1);}} // namespace bysint main() { return bys::Solver::main(/* bys::scanner.read<int>() */); }