pair<int, int> f_helper(int n) // Returns pair of f(n) and f(n + 1)
{
    if (n == 0)
        return make_pair(1, 1);
    if (n & 1)
    {
        pair<int, int> res = f_helper(n - 1);
        swap(res.first, res.second);
        res.second += res.first;
        return res;
    }
    pair<int, int> ans, res = f_helper(n / 2 - 1);
    ans.first = res.second * res.second + res.first * res.first;
    ans.second = res.second * (res.second + 2 * res.first);
    return ans;
}
int f(int n)
{
    return f_helper(n).first;
}