407851: GYM102900 G Fibonacci

In mathematics, the Fibonacci numbers, commonly denoted as $$$f_n$$$, is a sequence such that each number is the sum of the two preceding numbers, starting with $$$1$$$ and $$$1$$$. That is, $$$f_1 = 1, f_2 = 1$$$ and $$$f_n = f_{n-2} + f_{n-1}~(n \ge 3)$$$.

Thus, the beginning of the sequence is $$$1, 1, 2, 3, 5, 8, 13, 21,\ldots$$$ .

Given $$$n$$$, please calculate $$$\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$$$, where $$$g(x,y) = 1$$$ when $$$x \cdot y$$$ is even, otherwise $$$g(x,y) = 0$$$.

The only line contains one integer $$$n~(1\le n\le 10^9)$$$.

Output one number – $$$\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$$$.

3

2

10

24

100

2739