T566287 「2025 YAC Round 4」寺子屋的新老师

「2025 YAC Round 4」C 题 [橙](https://thwiki.cc/%E6%A9%99) 自从喝上进口奶粉后，就再也不喝当地产的低端奶粉了。为了能多赚点奶粉钱，[八云蓝](https://thbwiki.cc/%E5%85%AB%E4%BA%91%E8%93%9D) 决定取幻想乡寺子屋兼职当数学老师。

八云蓝不清楚寺子屋中学生的数学水平，在上课第一天就出了一道难题，一下子难倒了幻想乡最强——[琪露诺](https://www.thwiki.cc/%E7%90%AA%E9%9C%B2%E8%AF%BA) 等一众“优等生”。具体问题如下： 记 [斐波那契数列](https://oi-wiki.org/math/combinatorics/fibonacci/) 为数列 $f_n$。该数列满足如下递推公式： $$ f_n = \begin{cases} 1 & n = 1, 2 \\ f_{n-1} + f_{n-2} & n \ge 3 \end{cases} $$ 八云蓝给出一个 $n$，请求出数列的前 $n$ 项 $f_1, f_2, \ldots, f_n$ 中 有多少对二元组 $(i, j)$ 满足 $i < j$ 且两数乘积 $f_i \times f_j$ 为 **偶数**。

输入一行一个整数 $n$（$1 \le n \le 10^9$），如题意所示。

输出一个整数表示答案。