## Fibonacci Sequence (Harder)

View as PDF

Points: 20
Time limit: 2.0s
Memory limit: 64M
Author:

Problem type

quantum is not feeling well today, and has decided to create a more painful version of the simple Fibonacci problem.

Recall that the Fibonacci sequence is a well known sequence of numbers in which

You are given a number , find the Fibonacci number, modulo .

#### Input Specification

The first line of input will have the number .

#### Output Specification

The Fibonacci number, modulo .

#### Sample Input

26

#### Sample Output

121393