Preparing NOJ

# Product Oriented Recurrence

1000ms 262144K

## Description:

Let $f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$ for $x \ge 4$.

You have given integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$. Find $f_{n} \bmod (10^{9}+7)$.

## Input:

The only line contains five integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$ ($4 \le n \le 10^{18}$, $1 \le f_{1}$, $f_{2}$, $f_{3}$, $c \le 10^{9}$).

## Output:

Print $f_{n} \bmod (10^{9} + 7)$.

## Sample Input:

 5 1 2 5 3

## Sample Output:

 72900

## Sample Input:

 17 97 41 37 11

## Sample Output:

 317451037

## Note:

In the first example, $f_{4} = 90$, $f_{5} = 72900$.

In the second example, $f_{17} \approx 2.28 \times 10^{29587}$.

Info

Provider CodeForces

Code CF1182E

Tags

dpmathmatricesnumber theory

Submitted 23

Passed 13

AC Rate 56.52%

Date 07/21/2019 13:42:54

Related

Nothing Yet