409021: GYM103416 A Planet Nine

Astronomers have recently found a cosmic signal from a distant planet. World's best scientists have all confirmed that this is a communication signal sent by aliens. Moreover, they have established that these aliens have only nine fingers, hence, they use a numeral system in base 9, in other words, digits from $$$0$$$ to $$$8$$$. To challenge humans, these aliens came up with a puzzle. Many scientists solved the puzzle, but since the stakes are very high, they want you to confirm that their solution is correct as you are the smartest computer scientist on the planet. The puzzle is explained below.

Let $$$n$$$ be some positive integer, and $$$f(n)$$$ be a function that returns another positive integer that can be represented as $$$123456781011...n$$$ in base 9. In other words, $$$f(n)$$$ is a number which can be obtained by concatenating all the positive integers from 1 to n in their base 9 representations. The obtained number is also in base 9.

For example, for $$$n = 10$$$ (in base 10), $$$f(n) = 123456781011$$$, since $$$n = 11$$$ (in base 9). You need to find the remainder of dividing $$$f(n)$$$ by $$$4$$$.

Input consists of a single integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$ given in base 10.

Print a single integer equal to $$$f(n)$$$ modulo 4.

5

3