473.cpp

#include <vector>
#include <iostream>
#include <iomanip>

struct Int {
    static const int LIMIT = 1000000000;
    static const int WIDTH = 9;

    std::vector<int> digits;

    Int(int num = 0) : digits(1, num) { }

    Int(const std::vector<int> & v) : digits(v.begin(), v.end()) { }

    Int operator + (const Int & other) const {
        std::vector<int> answer;

        int s1 = (int) this->digits.size();
        int s2 = (int) other.digits.size();

        int carry = 0;

        for (int i = 0; i < s1 || i < s2; ++i) {
            int d1 = i < s1 ? this->digits[i] : 0;
            int d2 = i < s2 ? other.digits[i] : 0;
            carry += d1+d2;
            answer.push_back(carry % LIMIT);
            carry /= LIMIT;
        }

        if (carry)
            answer.push_back(carry);

        return Int(answer);
    }

    Int operator * (long long num) const {
        std::vector<int> answer;

        long long carry = 0;

        for (int i = 0; i < (int) digits.size(); ++i) {
            carry += num * digits[i];
            answer.push_back(carry % LIMIT);
            carry /= LIMIT;
        }

        if (carry)
            answer.push_back(carry);

        return Int(answer);
    }

    Int operator * (const Int & other) const {
        Int answer = 0;
        for (int i = (int) digits.size()-1; i >= 0; --i) {
            answer = answer * LIMIT;
            answer = answer + other * digits[i];
        }
        return answer;
    }
};

std::ostream & operator << (std::ostream & os, const Int & num) {
    os << num.digits.back();
    for (int i = (int) num.digits.size() - 2; i >= 0; --i)
        os << std::setw(Int::WIDTH) << std::setfill('0') << num.digits[i];
    return os;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<Int> c(1+n, 1);

    for (int i = 2; i <= n; ++i)
        c[i] = c[i-1]+c[i-2];

    std::cout << c[n]*c[n];

    return 0;
}