#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int INF = 1e9; const ll LINF = 1e18; template ostream& operator << (ostream& out,const pair& o){ out << "(" << o.first << "," << o.second << ")"; return out; } template ostream& operator << (ostream& out,const vector V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; } template ostream& operator << (ostream& out,const vector > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; } template ostream& operator << (ostream& out,const map mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; } /* 問題文============================================================ ================================================================= 解説============================================================= ================================================================ */ class bigint { private: static const int BASE = 10000000, LEN = 32; bool negative; std::vector a; bigint& normalize(); public: bigint(int x = 0); bigint(const std::string& s); bigint& operator = (const bigint& x); bigint& operator = (int x); bigint& operator = (const std::string& s); const bool operator < (const bigint& x) const; const bool operator > (const bigint& x) const; const bool operator <= (const bigint& x) const; const bool operator >= (const bigint& x) const; const bool operator != (const bigint& x) const; const bool operator == (const bigint& x) const; bigint operator -() const; bigint& operator += (const bigint& x); bigint& operator -= (const bigint& x); bigint& operator *= (const bigint& x); bigint& operator /= (const bigint& x); bigint& operator %= (const bigint& x); const bigint operator + (const bigint& x) const; const bigint operator - (const bigint& x) const; const bigint operator * (const bigint& x) const; const bigint operator / (const bigint& x) const; const bigint operator % (const bigint& x) const; friend std::pair divmod(const bigint& lhs, const bigint& rhs); friend std::istream& operator >> (std::ostream& is, bigint& x); //適当実装 friend std::ostream& operator << (std::ostream& os, const bigint& x); friend const bigint abs(bigint x); }; bigint& bigint::normalize() { int i = a.size()-1; while (i >= 0 && a[i] == 0) --i; a.resize(i+1); if (a.size() == 0) negative = false; return *this; } bigint::bigint(int x) : negative(x<0) { x = abs(x); for (; x > 0; x /= BASE) a.push_back(x % BASE); } bigint::bigint(const std::string& s): negative(false) { int p = 0; if (s[p] == '-') { ++p; negative = true; } else if (s[p] == '+') { ++p; } for (int i = s.size()-1, v = BASE; i >= p; --i, v*=10) { int x = s[i]-'0'; if (x < 0 || 9 < x) { std::cerr<<"error: parse error:"<= 0; --i) if (a[i] != x.a[i]) return (a[i] < x.a[i])^negative; return false; } const bool bigint::operator > (const bigint& x) const { return x<(*this); } const bool bigint::operator <= (const bigint& x) const { return !(x<(*this)); } const bool bigint::operator >= (const bigint& x) const { return !((*this) b(x.a); if ((*this < x) ^ negative) { a.swap(b); negative = !negative; } for (int i = 0, tmp = 0; i < a.size(); ++i) { a[i] += BASE - (inormalize(); } bigint& bigint::operator *= (const bigint& x) { negative ^= x.negative; std::vector c(a.size()*x.a.size()+1); for (int i = 0; i < a.size(); ++i) { long long tmp = 0; for (int j = 0; j < x.a.size(); ++j) { long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp; tmp = v / BASE; c[i+j] = (int)(v % BASE); } if (tmp) c[i+x.a.size()] += (int)tmp; } a.swap(c); return this->normalize(); } bigint& bigint::operator /= (const bigint& x) { return *this = divmod(*this,x).first; } bigint& bigint::operator %= (const bigint& x) { return *this = divmod(*this,x).second; } const bigint bigint::operator + (const bigint& x) const { bigint res(*this); return res += x; } const bigint bigint::operator - (const bigint& x) const { bigint res(*this); return res -= x; } const bigint bigint::operator * (const bigint& x) const { bigint res(*this); return res *= x; } const bigint bigint::operator / (const bigint& x) const { bigint res(*this); return res /= x; } const bigint bigint::operator % (const bigint& x) const { bigint res(*this); return res %= x; } std::pair divmod(const bigint& lhs, const bigint& rhs) { if (!rhs.a.size()) { std::cerr<<"error: division by zero"<= 0; --i) { r = r * bigint::BASE + lhs.a[i]; int head = 0, tail = bigint::BASE; if (r >= x) { while (head + 1 < tail) { int mid = (head + tail) / 2; if (x * bigint(mid) > r) tail = mid; else head = mid; } r -= x * head; } q.a.push_back(head); } reverse(q.a.begin(), q.a.end()); bool neg = lhs.negative ^ lhs.negative; q.negative = neg; r.negative = neg; return std::make_pair(q.normalize(), r.normalize()); } std::istream& operator >> (std::istream& is, bigint& x) { std::string tmp; is >> tmp; x = bigint(tmp); return is; } std::ostream& operator << (std::ostream& os, const bigint& x) { if (x.negative) os << '-'; if (!x.a.size()) os << 0; else os << x.a.back(); for (int i = (int)x.a.size()-2; i >= 0; --i) { os.width(bigint::LEN); os.fill('0'); os << x.a[i]; } return os; } const bigint abs(bigint x) { x.negative = false; return x; } typedef vector vec; typedef vector mat; /* 行列累乗 X = A^M*B A ( N*N行列) O(N^3 logM) */ mat mul(mat&A,mat&B){ mat C(A.size(),vec(B[0].size())); for(int i = 0; i < (int)A.size();i++){ for(int k = 0; k < (int)B.size();k++){ if(A[i][k] == 0) continue; for(int j = 0; j < B[0].size();j++){ C[i][j] = (C[i][j] + A[i][k]*B[k][j]); } } } return C; } mat pow(mat A,ll n){ mat B(A.size(),vec(A.size())); for(int i = 0; i < A.size();i++){ B[i][i] = 1; } while(n > 0){ if(n&1) B= mul(B,A); A = mul(A,A); n>>=1; } return B; } bigint calcfib(ll L){ mat A(2,vec(2,1)); A[1][1] = 0; return pow(A,L-1)[0][0]; } void solve(){ ll L; cin >> L; if(L == 2){ cout << 3 << endl; cout << "INF" << endl; return; } cout << L << endl; if(L%2 == 1){ cout << calcfib(L) << endl; }else{ bigint fib1 = calcfib(L),fib2 = calcfib(L/2); fib2*=fib2; cout << (fib1-fib2) << endl; } } int main(void) { cin.tie(0); ios_base::sync_with_stdio(false); solve(); return 0; }