407851: GYM102900 G Fibonacci

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Fibonaccitime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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$$$.

Input

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

Output

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

ExamplesInput
3
Output
2
Input
10
Output
24
Input
100
Output
2739

加入题单

上一题 下一题 算法标签: