Problem Description

In mathematics, the Fibonacci sequence, commonly denoted as \( f_n \), is a sequence where each number is the sum of the two preceding ones, starting from 1 and 1. That is, \( f_1 = 1 \), \( f_2 = 1 \), and \( f_n = f_{n-2} + f_{n-1} \) for \( n \geq 3 \).

Thus, the initial terms of the sequence are \( 1, 1, 2, 3, 5, 8, 13, 21, \ldots \).

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

Input Format

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

Output Format

Output a single number, which is the value of \( \sum_{i=1}^{n} \sum_{j=i+1}^{n} g(f_i, f_j) \).

Sample Input and Output

Sample Input #1

3

Sample Output #1

2

Sample Input #2

10

Sample Output #2

24

Sample Input #3

100

Sample Output #3

2739

见题面 Input 部分

见题面 Output 部分