#pragma GCC optimize("O3") #ifndef NAMESPACE_CONVOLUTION #define NAMESPACE_CONVOLUTION #include #include namespace convolution { /* MODINT CLASS FOR DOING NUMBER THEORETIC TRANSFORM (NTT) - arrays of 4 different mod-integers - works well with compiler option -O3, because it optimizes for MOD[i] = a * 2^k + 1 for small a * MOD[i]: mod values * GARNER[i]: equals MOD[s]^-1 (mod MOD[t]), for (s, t) = (0, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 3) BENCHMARK (2022.8.19) - AtCoder: 4.148 seconds for 10^9 multiplications with -O3 - ideone.com: 3.204 seconds for 5*10^8 multiplications with -O3 */ class ntt_modint { public: alignas(32) std::int64_t x[4]; alignas(32) static constexpr std::int64_t MOD[4] = { (51LL << 25) + 1LL, (54LL << 25) + 1LL, (60LL << 25) + 1LL, (63LL << 25) + 1LL }; alignas(32) static constexpr std::int64_t GARNER[6] = { 18LL, (5LL << 27) + 7LL, 10LL, (189LL << 23) + 6LL, 7LL, 21LL }; explicit ntt_modint() { x[0] = 0LL; x[1] = 0LL; x[2] = 0LL; x[3] = 0LL; } explicit ntt_modint(std::int64_t x0_, std::int64_t x1_, std::int64_t x2_, std::int64_t x3_) { x[0] = x0_; x[1] = x1_; x[2] = x2_; x[3] = x3_; for (int i = 0; i < 4; i++) { x[i] = (x[i] >= 0 ? x[i] % MOD[i] : (MOD[i] - (-x[i] % MOD[i]))) % MOD[i]; } } ntt_modint& operator+=(const ntt_modint& m) { for (int i = 0; i < 4; i++) { x[i] += m.x[i]; x[i] -= (x[i] >= MOD[i] ? MOD[i] : 0LL); } return (*this); } ntt_modint& operator-=(const ntt_modint& m) { for (int i = 0; i < 4; i++) { x[i] -= m.x[i]; x[i] += (x[i] < 0LL ? MOD[i] : 0LL); } return (*this); } ntt_modint& operator*=(const ntt_modint& m) { for (int i = 0; i < 4; i++) { x[i] = x[i] * m.x[i] % MOD[i]; } return (*this); } ntt_modint operator+(const ntt_modint& m) const { return ntt_modint(*this) += m; } ntt_modint operator-(const ntt_modint& m) const { return ntt_modint(*this) -= m; } ntt_modint operator*(const ntt_modint& m) const { return ntt_modint(*this) *= m; } __int128_t get() const { std::int64_t v[4]; int idx = 0; for (int i = 0; i < 4; i++) { v[i] = x[i]; for (int j = 0; j < i; j++) { v[i] = GARNER[idx++] * (v[i] - v[j] + MOD[i]) % MOD[i]; } } __int128_t res = v[0]; __int128_t mul = 1; for (int i = 0; i < 3; i++) { mul *= MOD[i]; res += v[i + 1] * mul; } return res; } }; constexpr std::int64_t ntt_modint::MOD[4]; constexpr std::int64_t ntt_modint::GARNER[6]; /* FUNCTION FOR NUMBER-THEORETIC TRANSFORM - FORWARD DIRECTION - do NTT in forward direction for an array x of size (1 << level) */ void forward_ntt(int level, ntt_modint* x) { ntt_modint f[25]; f[23] = ntt_modint(40, 103, 170, 551); // 2^25-th root for each mod (note: 23 = 25 - 2) for (int i = 22; i >= 0; i--) { f[i] = f[i + 1] * f[i + 1]; } for (int i = 0; i <= 23; i++) { f[i] *= ntt_modint(-1, -1, -1, -1); } int s = (1 << level); for (int i = level - 1; i >= 0; i--) { ntt_modint mult(1, 1, 1, 1); for (int j = 0; j < s; j += (2 << i)) { for (int k = j; k < j + (1 << i); k++) { ntt_modint xl = x[k]; ntt_modint xr = x[k + (1 << i)]; x[k] = xl + mult * xr; x[k + (1 << i)] = xl - mult * xr; } mult *= f[__builtin_ctz(~(j >> (i + 1)))]; } } } /* FUNCTION FOR NUMBER-THEORETIC TRANSFORM - REVERSE DIRECTION - do NTT in reverse direction for an array x of size (1 << level) */ void reverse_ntt(int level, ntt_modint* x) { ntt_modint f[25]; f[23] = ntt_modint(983983719, 1213823434, 698721702, 1392661172); // inverse of 2^25-th root for each mod (note: 23 = 25 - 2) for (int i = 22; i >= 0; i--) { f[i] = f[i + 1] * f[i + 1]; } for (int i = 0; i <= 23; i++) { f[i] *= ntt_modint(-1, -1, -1, -1); } int s = (1 << level); for (int i = 0; i < level; i++) { ntt_modint mult(1, 1, 1, 1); for (int j = 0; j < s; j += (2 << i)) { for (int k = j; k < j + (1 << i); k++) { ntt_modint xl = x[k]; ntt_modint xr = x[k + (1 << i)]; x[k] = xl + xr; x[k + (1 << i)] = (xl - xr) * mult; } mult *= f[__builtin_ctz(~(j >> (i + 1)))]; } } ntt_modint inv2 = ntt_modint((ntt_modint::MOD[0] + 1) / 2, (ntt_modint::MOD[1] + 1) / 2, (ntt_modint::MOD[2] + 1) / 2, (ntt_modint::MOD[3] + 1) / 2); ntt_modint powinv(1, 1, 1, 1); for (int i = 0; i < level; i++) { powinv *= inv2; } for (int i = 0; i < s; i++) { x[i] *= powinv; } } /* FUNCTION FOR CONVOLUTION - convolves two arrays a and b, and returns the output in array c * sa = (size of array a) * sb = (size of array b) * outputs the array c of size sa+sb-1 - works for 0 <= c[i] < 13196394894239664472536019622531432449 (~ 1.32 * 10^37) */ void convolve(int sa, int sb, std::int64_t *a, std::int64_t *b, __int128_t *c) { if (sa < sb) { std::swap(sa, sb); std::swap(a, b); } if (sb <= 48) { ntt_modint *va = new ntt_modint[sa]; ntt_modint *vb = new ntt_modint[sb]; ntt_modint *vc = new ntt_modint[sa + sb - 1]; for (int i = 0; i < sa; i++) { va[i] = ntt_modint(a[i], a[i], a[i], a[i]); } for (int i = 0; i < sb; i++) { vb[i] = ntt_modint(b[i], b[i], b[i], b[i]); } for (int i = 0; i < sa; i++) { for (int j = 0; j < sb; j++) { vc[i + j] += va[i] * vb[j]; } } for (int i = 0; i < sa + sb - 1; i++) { c[i] = vc[i].get(); } delete[] va; delete[] vb; delete[] vc; } else { for (int i = 0; i < sa + sb - 1; i++) { c[i] = 0; } int level = 0; while ((1 << level) < sb) { level += 1; } ntt_modint *va = new ntt_modint[2 << level]; ntt_modint *vb = new ntt_modint[2 << level]; for (int i = 0; i < sb; i++) { vb[i] = ntt_modint(b[i], b[i], b[i], b[i]); } forward_ntt(level + 1, vb); for (int i = 0; i < sa; i += (1 << level)) { int limit = std::min(sa - i, 1 << level); for (int j = 0; j < limit; j++) { va[j] = ntt_modint(a[i + j], a[i + j], a[i + j], a[i + j]); } for (int j = limit; j < (2 << level); j++) { va[j] = ntt_modint(); } forward_ntt(level + 1, va); for (int j = 0; j < (2 << level); j++) { va[j] *= vb[j]; } reverse_ntt(level + 1, va); for (int j = 0; j < limit + sb - 1; j++) { c[i + j] += va[j].get(); } } delete[] va; delete[] vb; } } } #endif // NAMESPACE_CONVOLUTION #ifndef CLASS_BASIC_INTEGER #define CLASS_BASIC_INTEGER #include #include class basic_integer { public: static constexpr int BASE_DIGITS = 14; static constexpr std::int64_t BASE = 100'000'000'000'000LL; int size_; int capacity_; std::int64_t *x; // constructor #1: default constructor, set value = 0 basic_integer() : size_(1), capacity_(1) { x = new std::int64_t[1]; x[0] = std::int64_t(0); } // constructor #2: copy constructor basic_integer(const basic_integer& b) : size_(b.size_), capacity_(b.capacity_) { x = new std::int64_t[capacity_]; for (int i = 0; i < capacity_; i++) { x[i] = b.x[i]; } } // copy operator basic_integer& operator=(const basic_integer& b) { size_ = b.size_; capacity_ = b.capacity_; delete[] x; x = new std::int64_t[capacity_]; for (int i = 0; i < capacity_; i++) { x[i] = b.x[i]; } return (*this); } // destructor ~basic_integer() { delete[] x; } // root function #1: change capacity void change_capacity(int new_capacity_) { if (capacity_ == new_capacity_) { return; } int limit = std::min(capacity_, new_capacity_); std::int64_t *tx = new std::int64_t[limit]; for (int i = 0; i < limit; i++) { tx[i] = x[i]; } delete[] x; x = new std::int64_t[new_capacity_]; for (int i = 0; i < limit; i++) { x[i] = tx[i]; } delete[] tx; for (int i = limit; i < new_capacity_; i++) { x[i] = 0LL; } capacity_ = new_capacity_; } // root function #2: digits(), returns the number of digits int digits() const { std::int64_t v = x[size_ - 1]; int digit = 0; do { digit += 1; v /= 10; } while (v != 0LL); return digit + (size_ - 1) * BASE_DIGITS; } // root function #3. comparison function int compare(const basic_integer& b) const { // if self < b, returns -1 // if self == b, returns 0 // if self > b, returns +1 if (size_ != b.size_) { return (size_ < b.size_ ? -1 : +1); } for (int i = size_ - 1; i >= 0; i--) { if (x[i] != b.x[i]) { return (x[i] < b.x[i] ? -1 : +1); } } return 0; } // operator #1. += operator basic_integer& operator+=(const basic_integer& b) { change_capacity(std::max(capacity_, b.capacity_)); for (int i = 0; i < b.size_; i++) { x[i] += b.x[i]; } size_ = std::max(size_, b.size_); for (int i = 0; i < size_ - 1; i++) { if (x[i] >= BASE) { x[i] -= BASE; x[i + 1] += 1; } else if (i >= b.size_) { break; } } if (x[size_ - 1] >= BASE) { if (size_ == capacity_) { change_capacity(capacity_ * 2); } x[size_ - 1] -= BASE; x[size_] += 1; size_ += 1; } return (*this); } // operator #2. -= operator basic_integer& operator-=(const basic_integer& b) { for (int i = 0; i < b.size_; i++) { x[i] -= b.x[i]; } for (int i = 0; i < size_; i++) { if (x[i] < 0) { x[i] += BASE; x[i + 1] -= 1; } else if (i >= b.size_) { break; } } while (size_ >= 2 && x[size_ - 1] == 0) { size_ -= 1; } int new_capacity_ = capacity_; while (size_ <= new_capacity_ / 2) { new_capacity_ /= 2; } change_capacity(new_capacity_); return (*this); } // operator #3. *= operator basic_integer& operator*=(const basic_integer& b) { __int128_t *c = new __int128_t[size_ + b.size_ - 1]; convolution::convolve(size_, b.size_, x, b.x, c); int new_size_ = size_ + b.size_; int new_capacity_ = std::max(capacity_, b.capacity_); if (new_size_ > new_capacity_) { new_capacity_ *= 2; } change_capacity(new_capacity_); __int128_t carry = 0; for (int i = 0; i < size_ + b.size_ - 1; i++) { carry += c[i]; x[i] = carry % BASE; carry /= BASE; } x[size_ + b.size_ - 1] = carry; while (new_size_ >= 2 && x[new_size_ - 1] == 0) { new_size_ -= 1; } size_ = new_size_; while (size_ <= new_capacity_ / 2) { new_capacity_ /= 2; } change_capacity(new_capacity_); return (*this); } }; #endif // CLASS_BASIC_INTEGER #ifndef CLASS_BIG_INTEGER #define CLASS_BIG_INTEGER #include #include #include class big_integer { private: basic_integer content; bool negative; public: big_integer() : content(basic_integer()), negative(false) {}; // constructor by string (e.g. "123", "4567", "0089", "0") big_integer(const std::string& s) { // check the validity if (!(s != "" && (('0' <= s[0] && s[0] <= '9') || s[0] == '-'))) { throw std::invalid_argument("big_integer: string does not represent an integer"); } int l = (s[0] != '-' ? 0 : 1); for (int i = l; i < int(s.size()); i++) { if (!('0' <= s[i] && s[i] <= '9')) { throw std::invalid_argument("big_integer: string does not represent an integer"); } } while (s[l] == '0' && l != int(s.size()) - 1) { l += 1; } content.size_ = (int(s.size()) - l + basic_integer::BASE_DIGITS - 1) / basic_integer::BASE_DIGITS; content.capacity_ = 1; while (content.capacity_ < content.size_) { content.capacity_ <<= 1; } content.x = new std::int64_t[content.capacity_]; for (int i = 0; i < content.capacity_; i++) { content.x[i] = 0LL; } for (int i = l; i < int(s.size()); i++) { int pos = (int(s.size()) - i - 1) / basic_integer::BASE_DIGITS; content.x[pos] = content.x[pos] * 10 + int(s[i] - '0'); } negative = (s[0] == '-' && (content.size_ >= 2 || content.x[0] != 0LL) ? true : false); } // to_string() : convert integer to string std::string to_string() const { int digit = content.digits(); std::string res(digit + (negative ? 1 : 0), '?'); if (negative) { res[0] = '-'; } for (int i = 0; i < content.size_; i++) { std::int64_t v = content.x[i]; int limit = std::min(basic_integer::BASE_DIGITS * (i + 1), digit); for (int j = basic_integer::BASE_DIGITS * i; j < limit; j++) { res[digit - j - (negative ? 0 : 1)] = char(v % 10 + '0'); v /= 10; } } return res; } // digits() : returns the number of digits int digits() const { return content.digits(); } // comparison operator #1. == operator bool operator==(const big_integer& b) const { return (negative == b.negative && content.compare(b.content) == 0); } // comparison operator #2. != operator bool operator!=(const big_integer& b) const { return (negative != b.negative || content.compare(b.content) != 0); } // comparison operator #3. < operator bool operator<(const big_integer& b) const { return (negative == b.negative ? content.compare(b.content) == -1 : negative); } // comparison operator #4. > operator bool operator>(const big_integer& b) const { return (negative == b.negative ? content.compare(b.content) == +1 : b.negative); } // comparison operator #5. <= operator bool operator<=(const big_integer& b) const { return (negative == b.negative ? content.compare(b.content) != +1 : negative); } // comparison operator #6. >= operator bool operator>=(const big_integer& b) const { return (negative == b.negative ? content.compare(b.content) != -1 : b.negative); } // operator A1. += operator big_integer& operator+=(const big_integer& b) { if (negative == b.negative) { content += b.content; } else if (content.compare(b.content) == -1) { content = (basic_integer(b.content) -= content); negative = !negative; } else { content -= b.content; if (negative && content.size_ == 1 && content.x[0] == 0) { negative = false; } } return (*this); } // operator A2. -= operator big_integer& operator-=(const big_integer& b) { if (negative != b.negative) { content += b.content; } else if (content.compare(b.content) == -1) { content = (basic_integer(b.content) -= content); negative = !negative; } else { content -= b.content; if (negative && content.size_ == 1 && content.x[0] == 0) { negative = false; } } return (*this); } // operator A3. *= operator big_integer& operator*=(const big_integer& b) { content *= b.content; negative = (negative ? !b.negative : b.negative); if (negative && content.size_ == 1 && content.x[0] == 0) { negative = false; } return (*this); } // operator B1. + operator big_integer operator+(const big_integer& b) const { return big_integer(*this) += b; } // operator B2. - operator big_integer operator-(const big_integer& b) const { return big_integer(*this) -= b; } // operator B3. * operator big_integer operator*(const big_integer& b) const { return big_integer(*this) *= b; } }; #endif #include void fibonacci(int n, big_integer &x, big_integer &y) { if (n == 0) { x = big_integer("0"), y = big_integer("1"); return; } if (n & 1) { fibonacci(n - 1, y, x); y += x; } else { big_integer xd, yd; fibonacci(n >> 1, xd, yd); big_integer zd = xd * xd; y = zd + yd * yd; x = xd * yd * big_integer("2") - zd; } } int main() { int n; std::cin.tie(0); std::ios_base::sync_with_stdio(false); std::cin >> n; if(n == 2) { std::cout << 3 << '\n'; std::cout << "INF\n"; } else { std::cout << n << '\n'; big_integer x, y; fibonacci(n, x, y); if (n & 1) { std::cout << x.to_string() << '\n'; } else { big_integer z; fibonacci(n >> 1, y, z); std::cout << (x - y * y).to_string() << '\n'; } } return 0; }