TLE '15 P4 - Olympiads Homework

View as PDF

Submit solution


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

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

\dbinom{n}{k}=\begin{cases} \dfrac{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 problemsetter knows the techniques* for this problem, and wants to tell you a secret:

\dbinom{N}{0}+\dbinom{N}{4}+\dbinom{N}{8}+\dots+\dbinom{N}{4N} = \dfrac{2^N}{4}+\dfrac{\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 problemsetter is now.

Input Specification

One integer, containing the value of N (1 \le N \le 10^{18}).

Output Specification

Output the value of:

\dbinom{N}{0}+\dbinom{N}{4}+\dbinom{N}{8}+\dots+\dbinom{N}{4N}

The value should be outputted \bmod 10^9+13, a product of two prime numbers.

Sample Input

13

Sample Output

2016

Comments


  • 0
    jlsajfj  commented on March 11, 2016, 5: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...


    • -8
      Kirito  commented on May 11, 2016, 6:52 p.m. edited

      This comment is hidden due to too much negative feedback. Click here to view it.