Fibonacci Pair Sum

In mathematics, the Fibonacci numbers, commonly denoted as \(f_n\), form a sequence where each number is the sum of the two preceding numbers, starting with \(f_1 = 1\) and \(f_2 = 1\). For \(n \geq 3\), the sequence is defined as:

\(f_n = f_{n-2} + f_{n-1}\)

This produces the sequence: 1, 1, 2, 3, 5, 8, 13, 21, …

Given a positive integer \(n\), your task is to compute:

\(S = \sum_{i=1}^{n} \sum_{j=i+1}^{n} g(f_i,f_j)\)

where the function \(g(x,y)\) is defined as follows:

\(g(x,y)=\begin{cases}1,&\text{if } x\cdot y \text{ is even}\\0,&\text{otherwise}\end{cases}\)

inputFormat

The input consists of a single integer \(n\) (with \(1 \leq n \leq 10^6\)).

outputFormat

Output a single integer representing the computed summation \(S\).

sample

1

0