#include #include #include using namespace std; template class mod_int { private: unsigned int value = 0; constexpr static bool is_prime(const unsigned int arg) noexcept { for (unsigned int i = 2; i * i <= arg; ++i) if (arg % i == 0) return false; return true; } constexpr static unsigned int pow_mod(unsigned int a, size_t b) noexcept { if (MOD == 1) return 0; unsigned int ans = 1; a %= MOD; for (; b != 0; b >>= 1, a = static_cast(a) * a % MOD) if (b & 1) ans = ans * static_cast(a) % MOD; return ans; } public: constexpr mod_int() noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); } template constexpr mod_int(const T arg) noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); value = (unsigned int)(arg % MOD); } constexpr mod_int operator+(const mod_int other) const noexcept { return mod_int(this->value >= MOD - other.value ? this->value - (MOD - other.value) : this->value + other.value); } constexpr mod_int operator-(const mod_int other) const noexcept { return mod_int(this->value >= other.value ? this->value - other.value : MOD - (other.value - this->value)); } constexpr mod_int operator*(const mod_int other) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast(this->value) * other.value % MOD); else return mod_int(this->value * other.value % MOD); } constexpr mod_int operator/(const mod_int other) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int(static_cast(this->value) * pow_mod(other.value, MOD - 2) % MOD); else return mod_int(this->value * pow_mod(other.value, MOD - 2) % MOD); } template constexpr mod_int operator+(T arg) const noexcept { arg %= MOD; return mod_int(value >= MOD - static_cast(arg) ? value - (MOD - static_cast(arg)) : value + static_cast(arg)); } template constexpr mod_int operator-(T arg) const noexcept { arg %= MOD; return mod_int(value >= static_cast(arg) ? value - static_cast(arg) : MOD - (static_cast(arg) - value)); } template constexpr mod_int operator*(T arg) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast(value) * (arg % MOD) % MOD); else return mod_int(value * static_cast(arg % MOD) % MOD); } template constexpr mod_int operator/(T arg) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int(static_cast(value) * pow_mod(static_cast(arg % MOD), MOD - 2) % MOD); else return mod_int(value * pow_mod(static_cast(arg % MOD), MOD - 2) % MOD); } constexpr mod_int& operator+=(const mod_int other) noexcept { if (this->value >= MOD - other.value) this->value -= (MOD - other.value); else this->value += other.value; return *this; } constexpr mod_int& operator-=(const mod_int other) noexcept { if (this->value >= other.value) this->value -= other.value; else this->value += (MOD - other.value); return *this; } constexpr mod_int& operator*=(const mod_int other) noexcept { if constexpr (MOD >= (1u << 16)) this->value = static_cast(this->value) * other.value % MOD; else this->value = this->value * other.value % MOD; return *this; } constexpr mod_int& operator/=(const mod_int other) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) this->value = static_cast(this->value) * pow_mod(other.value, MOD - 2) % MOD; else this->value = this->value * pow_mod(other.value, MOD - 2) % MOD; return *this; } template constexpr mod_int& operator+=(T arg) noexcept { arg %= MOD; if (value >= MOD - arg) value -= (MOD - arg); else value += arg; return *this; } template constexpr mod_int& operator-=(T arg) noexcept { arg %= MOD; if (value >= arg) value -= arg; else value += (MOD - arg); return *this; } template constexpr mod_int& operator*=(T arg) noexcept { if constexpr (MOD >= (1u << 16)) value = static_cast(value) * (arg % MOD) % MOD; else value = value * (arg % MOD) % MOD; return *this; } template constexpr mod_int& operator/=(T arg) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast(value) * pow_mod(static_cast(arg % MOD), MOD - 2) % MOD; else value = value * pow_mod(static_cast(arg % MOD), MOD - 2) % MOD; return *this; } constexpr mod_int& operator++() noexcept { if (value + 1 == MOD) value = 0; else ++value; return *this; } constexpr mod_int operator++(int) noexcept { const auto temp = value; if (value + 1 == MOD) value = 0; else ++value; return mod_int(temp); } constexpr mod_int& operator--() noexcept { if (value == 0) value = MOD - 1; else --value; return *this; } constexpr mod_int operator--(int) noexcept { const auto temp = value; if (value == 0) value = MOD - 1; else --value; return *this; } constexpr bool operator==(const mod_int other) const noexcept { return this->value == other.value; } constexpr bool operator!=(const mod_int other) const noexcept { return this->value != other.value; } constexpr bool operator<(const mod_int other) const noexcept { return this->value < other.value; } constexpr bool operator<=(const mod_int other) const noexcept { return this->value <= other.value; } constexpr bool operator>(const mod_int other) const noexcept { return this->value > other.value; } constexpr bool operator>=(const mod_int other) const noexcept { return this->value >= other.value; } template constexpr bool operator==(const T arg) const noexcept { static_assert(is_integral::value, "T is not an integral type."); return value == arg; } template constexpr bool operator!=(const T arg) const noexcept { static_assert(is_integral::value, "T is not an integral type."); return value != arg; } template constexpr bool operator<(const T arg) const noexcept { static_assert(is_integral::value, "T is not an integral type."); return value < arg; } template constexpr bool operator<=(const T arg) const noexcept { static_assert(is_integral::value, "T is not an integral type."); return value <= arg; } template constexpr bool operator>(const T arg) const noexcept { static_assert(is_integral::value, "T is not an integral type."); return value > arg; } template constexpr bool operator>=(const T arg) const noexcept { static_assert(is_integral::value, "T is not an integral type."); return value >= arg; } operator unsigned int() const noexcept { return this->value; } constexpr mod_int pow_mod(unsigned long long times) { if (MOD == 1) return 0; mod_int ans = 1; unsigned int a = this->value; for (; times != 0; times >>= 1, a = static_cast(a) * a % MOD) if (times & 1) ans.value = static_cast(ans.value) * a % MOD; return ans; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); uint32_t N, i; cin >> N; if (N == 1) { cout << "1\n"; return 0; } array, 3> dp_cur, dp_prev; dp_cur[0] = dp_cur[1] = 1, dp_cur[2] = 0; for (i = 2; i != N; ++i) { dp_cur.swap(dp_prev); dp_cur[0] = dp_prev[2]; dp_cur[1] = dp_prev[0] + dp_prev[2]; dp_cur[2] = dp_prev[1]; } cout << dp_cur[0] + dp_cur[1] + dp_cur[2] << '\n'; return 0; }