Bibi is currently learning maths. He just learned fibonacci. Fibonacci sequence takes the 2 previous numbers and sum it up to get the current number of the sequence. Now he wonders, what if we take 4 numbers instead of 2?

Given: f(1) = 0 f(2) = 0 f(3) = 1 f(4) = 1 Find the N-th term of the quadbonacci sequence!

The numbers may be too large too contain, so modulo it by 10⁹ + 7.

Input Format

The only input will be a single integer N.

Constraints

1 N 75

Output Format

Output the result of Quadbonacci(N), the N-th term of the sequence.

Sample Input 0

3 

Sample Output 0

1 

Sample Input 2

5 

Sample Output 2

2

c++ stdio.h