TLE '15 P4 - Olympiads Homework - DMOJ: Modern Online Judge

TLE '15 P4 - Olympiads Homework

Points: 12 (partial)

Time limit: 0.75s

Memory limit: 64M

Authors:

Problem type

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$ $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}$ $(\binom{N}{0}) + (\binom{N}{4}) + (\binom{N}{8}) + \dots + (\binom{N}{4 N})$ . The exact value of $N$ $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$ $mod 10^{9} + 13$ .

jlsajfj also stated, quite plainly, these two pieces of info from his math class:

$n!$ $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}$ $n! = {\begin{cases} 1 & if n = 0 \\ n \times (n - 1)! & if n \geq 1 \end{cases}$

$\dbinom n k$ $(\binom{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}$ $(\binom{n}{k}) = {\begin{cases} \frac{n!}{k! \times (n - k)!} & if 0 \leq k \leq n \\ 0 & if k < 0 or k > n \end{cases}$

Can you use a computer and find the answer to jlsajfj's math problem in less than $1$ $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$ $(\binom{N}{0}) + (\binom{N}{4}) + (\binom{N}{8}) + \dots + (\binom{N}{4 N}) = \frac{2^{N}}{4} + \frac{{\sqrt{2}}^{N} \times \cos (45^{\circ} \times N)}{2}$

This formula is valid for any positive integer $N$ $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$ $N$ $(1 \le N \le 10^{18})$ $(1 \leq N \leq 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$ $(\binom{N}{0}) + (\binom{N}{4}) + (\binom{N}{8}) + \dots + (\binom{N}{4 N}) mod 10^{9} + 13$

Note that $10^9+13$ $10^{9} + 13$ is a product of two prime numbers.

Sample Input

Copy

Sample Output

Copy

Comments

0

jlsajfj commented on March 11, 2016, 10:40 p.m. ← edit 2 →

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

-12

Kirito commented on May 11, 2016, 10:52 p.m. ← edited →

Why are there so many math problems in TLE? I'm bad at math.

This comment is hidden due to too much negative feedback. Show it anyway.