Description

在数学中，斐波那契数列通常用 $f_n$ 表示，是一个序列，其中每个数字是前两个数字之和，起始为 $1$ 和 $1$。即 $f_1 = 1, f_2 = 1$，且 $f_n = f_{n-2} + f_{n-1}~(n \ge 3)$。

因此，该序列的开头是 $1, 1, 2, 3, 5, 8, 13, 21,\ldots$。

给定 $n$，请计算 $\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$，其中 $g(x,y) = 1$ 当 $x \cdot y$ 为偶数时，否则 $g(x,y) = 0$。

Input Format

唯一一行包含一个整数 $n~(1\le n\le 10^9)$。

Output Format

输出一个数字 -- $\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$。

3

2

10

24

100

2739

Hint

题面翻译由 ChatGPT-4o 提供。