/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //@formatter:off #pragma GCC optimize("Ofast") #include using namespace std; //@formatter:off #define rep(i, n) for (int i = 0; i < (n); ++i) #define drep(i, n) for (int i = (n)-1; i >= 0; --i) #define srep(i, s, t) for (int i = s; i < t; ++i) #define rng(a) a.begin(), a.end() #define rrng(a) a.rbegin(), a.rend() using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VVVI = vector; using VVVVI = vector; using VL = vector; using VVL = vector; using VVVL = vector; using VVVVL = vector; using VP = vector

; using VVP = vector>; using VS = vector; using VC = vector; using VVC = vector>; using VD = vector; using VVD = vector>; using VVVD = vector; using I_I = pair; const int INF = (int)1e9 + 10; // int max > 2*10^9 const long long INFL = (ll)2e18 + 10; // ll max > 9*10^18 const int JU_5 = 100000; const int JU_6 = 1000000; const ll JU_9 = 1000000000; const ll JU_18 = JU_9*JU_9; #define YES cout << "YES" << endl #define NO cout << "NO" << endl #define Yes cout << "Yes" << endl #define No cout << "No" << endl template pair operator+(const pair &a, const pair &b) { return make_pair(a.first + b.first, a.second + b.second); } template pair operator-(const pair &a, const pair &b) { return make_pair(a.first - b.first, a.second - b.second); } template pair operator*(const pair &a, const pair &b) { return make_pair(a.first * b.first, a.second * b.second); } template pair operator/(const pair &a, const pair &b) { return make_pair(a.first / b.first, a.second / b.second); } // #define MOD 1000000007 #define MOD 998244353 #define pmod(x,y) ((x%y)+y)%y /********** libs **********/ //@formatter:off // jhelper 用変数 ostream *__cout; istream *__cin; void _init_io(std::istream &cin, std::ostream &cout) { // 入出力高速化用 ios::sync_with_stdio(false); cin.tie(nullptr); cout << std::setprecision(30); // jhelper 用 __cout = &cout; __cin = &cin; } //@formatter:off /* デバッグ用 出力 */ template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v: vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } // print like python // src: https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed ///////////////////////////////////////////////////////// void print() { *__cout << endl; } template void print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; print(forward(tail)...); } template void print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } *__cout << endl; } template void print(vector> &df) { for (auto &vec: df) { print(vec); } } // endl なし void Print() {} template void Print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; Print(forward(tail)...); } template void Print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } } //@formatter:off /* * org: https://atcoder.jp/contests/abc213/submissions/24901856 * jhelper で使用するため, 全部 cin での入力にしている. (現状のレベルでは困らないので) */ template void scan(T& a){ *__cin >> a; } template void scan(vector&); template void scan(pair&); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } void in(){} template void in(T&... a){ (void)initializer_list{ (scan(a), 0)... }; } #define let_v(type,name,...) vectorname(__VA_ARGS__) #define let_V(type,name,size) vectorname(size);in(name) #define let_vv(type,name,h,...) vector>name(h,vector(__VA_ARGS__)) #define let_VV(type,name,h,w) vector>name(h,vector(w));in(name) #define let_vvv(type,name,h,w,...) vector>>name(h,vector>(w,vector(__VA_ARGS__))) #define let_vvvv(type,name,h,w,x,...) vector>>>name(h,vector>>(w,vector>(x,vector(__VA_ARGS__)))) /* string 入力を vector で受け取るみたいな */ vector let_CharVec() { string s; *__cin >> s; return {s.begin(), s.end()}; } //@formatter:off //ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } template bool chmax(T& a, C b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, C b) { if (a > b) { a = b; return true; } return false; } template T sum(const vector& v) { T res = 0; for (size_t i = 0; i < v.size(); ++i) res += v[i]; return res; } template T min(T a, C b) { return a <= b ? a : T(b); } template T max(T a, C b) { return a >= b ? a : T(b); } template vector> idx_pair(vector &vals) { vector> ans; rep(i, vals.size()) { ans.emplace_back(vals[i], i); } return ans; } /* ids 順に並び替え */ template vector sort_with_ids(vector &vals,vector &ids){ vector res; for(int i = 0;i int argmax(vector &vals){ if(vals.size()==0)return -1; int res=0; for(int i = 1;ivals[res])res=i; } return res; } template int argmin(vector &vals){ if(vals.size()==0)return -1; int res=0; for(int i = 1;i= mod) x -= mod; return *this; } mint &operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint &operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { mint res(*this); return res += a; } mint operator-(const mint a) const { mint res(*this); return res -= a; } mint operator*(const mint a) const { mint res(*this); return res *= a; } // bool operator==(const mint a) const { // return this->x == a.x; // } // x^t mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; // 桁ずらし if (t & 1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod - 2); } mint &operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res /= a; } }; istream &operator>>(istream &is, mint &a) { return is >> a.x; } ostream &operator<<(ostream &os, const mint &a) { return os << a.x; } /** * mint を使った combination 計算 */ mint calc_cmb(ll n, ll m) { if (n - m < m) m = n - m; mint x = 1; mint d = 1; for(int i=0;i kaijo; vector gyaku; ll r(ll x) { while (x % MOD == 0) x /= MOD; return x; } // xの mod 進数 int rcnt(ll x) { if (x <= 0) return 0; return rcnt(x / MOD) + x / MOD; } Comb(int mn) : n(mn + 1), kaijo(mn + 1), gyaku(mn + 1) { // mod で割り切れるだけ割ったときの nCm を求められるように, 階乗と逆元を求める kaijo[0] = 1; for (int i = 1; i < n; i++) { kaijo[i] = kaijo[i - 1] * r(i); } gyaku[n - 1] = kaijo[n - 1].pow(MOD - 2); for (int i = n - 1; i > 0; i--) { gyaku[i - 1] = gyaku[i] * r(i); } } mint nCm(int n, int m) { if (n < m || m < 0) return 0; if(m==0)return mint(1); int cnt1 = rcnt(n); int cnt2 = rcnt(n - m) + rcnt(m); if (cnt1 > cnt2) return mint(0); assert(n n) return 0; if(n==m)return kaijo[n]; int cnt1 = rcnt(n); int cnt2 = rcnt(n - m); if (cnt1 > cnt2) return mint(0); return kaijo[n] * gyaku[n - m]; } // 重複組合せ. n 種類の中から重複を許し m 個とる mint nHm(int n, int m) { int l = n + m - 1; int r = n - 1; if (l < 0 || r < 0) return mint(0); return nCm(l, r); } }; using VMI = vector; using VVMI = vector>; using VVVMI = vector; // #include "../library/string/utils.cpp" // #include "../library/math/utils.cpp" /**************************/ /** * 行列積 a*b */ template vector> prod(vector>& a, vector>& b) { vector> res(a.size(), vector(b[0].size(), 0)); rep(i, a.size()) { rep(j, b[0].size()) { rep(k, b.size()) { res[i][j] += a[i][k] * b[k][j]; } } } return res; } /** * 行列と vector の積 A*b */ template vector prodVec(vector>& a, vector& b) { vector> b2; // reshape rep(i, b.size()) { b2.push_back({b[i]}); }; auto tmp = prod(a, b2); vector res; rep(i, a.size()) { res.push_back(tmp[i][0]); } return res; } /** * 行列累乗 */ template struct MatrixExp { vector> _A; MatrixExp(vector>& A) : _A(A) {} // 演算は半環を満たしていれば良いトノコト // https://www.slideshare.net/chokudai/abc009 // 掛け算に相当する演算 T mul(T a, T b) { return a * b; } // 足し算に相当する演算 T plus(T a, T b) { return a + b; } // 行列積 vector> prod(vector>& a, vector>& b) { // TODO: 初期化は 0 にしている vector> res(a.size(), vector(b[0].size(), 0)); rep(i, a.size()) { rep(j, b[0].size()) { rep(k, b.size()) { res[i][j] = plus(res[i][j], mul(a[i][k], b[k][j])); } } } return res; } /** * 行列累乗を求める * @param x vector * @param n 乗数 */ vector solve(vector& x, ll n) { vector> x2; // reshape rep(i, x.size()) { x2.push_back({x[i]}); }; vector> A = _A; while (n) { if (n & 1) { x2 = prod(A, x2); } A = prod(A, A); n >>= 1; } vector res; rep(i, x.size()) { res.push_back(x2[i][0]); } return res; } }; class No2156 { public: void solve(std::istream &cin, std::ostream &cout) { _init_io(cin, cout); int t = 1; // cin >> t; while (t--) _solve(cin, cout); } //@formatter:on void _solve(std::istream &cin, std::ostream &cout) { // code ll n; cin >> n; VVMI x{{1}, {0}}; if (n < 2) { print(n); return; } VVMI A = {{1, 1}, {1, 0}}; ll N = n + 1; srep(i, 0, 19) { if (N & (1ll << i)) { x=prod(A, x); } A = prod(A, A); } print(x[1][0]-1); } }; int main() { No2156 solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }