Sum of Digit Sums of Fibonacci Numbers modulo 9

Define \(S(x)\) as the sum of the digits of \(x\). For example, \(S(14)=1+4=5\) and \(S(114514)=1+1+4+5+1+4=16\).

Also, define \(fib(x)\) as the \(x\)th Fibonacci number with \(fib(1)=fib(2)=1\) and \(fib(x)=fib(x-1)+fib(x-2)\) for \(x\ge3\).

Given an integer \(n\), compute the following value:

\[ \left(S(fib(1))+S(fib(2))+\cdots+S(fib(n))\right) \bmod 9 \]

Note: The notation \(\bmod 9\) means taking the remainder after division by 9.

inputFormat

The input consists of a single integer \(n\), representing the number of Fibonacci numbers to consider.

Input Format:

 n

outputFormat

Output a single integer, the value of \((S(fib(1))+S(fib(2))+\cdots+S(fib(n))) \bmod 9\).

sample

1

1