Fibonacci Sum Function Challenge

Given the Fibonacci sequence defined as follows:

\[ \operatorname{fib}(n)=\begin{cases}1&\text{if } n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&\text{if } n>2 \end{cases} \]

We further define a function (note that for \(n<1\), the value is \(0\)):

\[ f(n)=\sum_{i=1}^n \operatorname{fib}^2(i) \]

Your task is to compute the following sum modulo \(p\):

\[ S=\sum_{i=1}^n \operatorname{fib}(i)\cdot\Bigl(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i)\Bigr) \pmod{p} \]

Note: \(\operatorname{fib}^2(x)\) stands for \((\operatorname{fib}(x))^2\), and by definition \(f(n)=0\) for \(n<1\).

inputFormat

The input consists of two space-separated integers \(n\) and \(p\) on a single line:

• \(n\): the number of terms in the series.
• \(p\): the modulus.

outputFormat

Output a single integer representing the value of \(S\) modulo \(p\).

sample

1 100

2