An Olympiads math teacher has put an unusually difficult math problem into the grade 10 Olympiads math homework. Being forced to do homework, the unsuspecting jlsajfj worked on the problem for less than 
~1~ second, wrote down a random number, then immediately gave up. This math problem is apparently too difficult for jlsajfj, so he activated his second line of defense: bothering random friends. So far, jlsajfj's acquaintances were all lazy and ignorant unable to solve the problem and suggested nothing useful. That is why jlsajfj has decided to bother you next.
According to jlsajfj, the math problem requires you to write down the value of 
~\dbinom N 0+\dbinom N 4+\dbinom N 8+\dots+\dbinom N {4N}~. The exact value of 
~N~ appears to be secret, and jlsajfj wants you to do the same question over and over. Since the answer may contain a lot of digits, you decided to be devious and return the answers 
~\bmod 10^9+13~.
jlsajfj also stated, quite plainly, these two pieces of info from his math class:
~n!~ is the factorial, which is
$$\displaystyle n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n \ge 1 \end{cases}$$
~\dbinom n k~ is the combination, which is
$$\displaystyle \binom n k = \begin{cases} \frac{n!}{k! \times (n-k)!} & \text{if } 0 \le k \le n \\ 0 & \text{if } k < 0 \text{ or } k > n \end{cases}$$
Can you use a computer and find the answer to jlsajfj's math problem in less than ~1~ second?
Note
The problem setter knows the techniques* for this problem, and wants to tell you a secret:
$$\displaystyle \binom N 0+\binom N 4+\binom N 8+\dots+\binom N {4N} = \frac{2^N} 4+\frac{\sqrt{2}^N \times \cos(45^\circ \times N)} 2$$
This formula is valid for any positive integer ~N~.
*It was from an Olympiads math teacher. You probably know who the problem setter is now.
Input Specification
One integer, containing the value of ~N~ 
~(1 \le N \le 10^{18})~.
Output Specification
Output the value of:
$$\displaystyle \binom N 0+\binom N 4+\binom N 8+\dots+\binom N {4N} \bmod 10^9+13$$
Note that 
~10^9+13~ is a product of two prime numbers.
Sample Input
13
Sample Output
2016
Comments
all lazy and ignorant unable to solve the problem and suggested nothing useful. That is why jlsajfj has decided to bother you next. JASONNNNNNNNN LAAAAZYYYY
Edit: And you had to make my question the type of implementation i hate...
This comment is hidden due to too much negative feedback. Show it anyway.