Truy hồi tích luỹ

Cho dãy số $f_x$ được xác định bởi quan hệ truy hồi:

$$f_x=c^{2x-6}·f_{x-1}·f_{x-2}·f_{x-3}\text{với mọi }x\ge 4.$$

Cho trước các số nguyên $n$, $f_1$, $f_2$, $f_3$ và $c$. Hãy tính $f_{n}mod({10}^9+7)$.

Dữ liệu vào

Một dòng duy nhất chứa năm số nguyên $n$, $f_1$, $f_2$, $f_3$, $c$.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị $f_{n}mod({10}^9+7)$.

Ràng buộc

• $4\le n\le {10}^{18}$
• $1\le f_1,f_2,f_3,c\le {10}^9$

Ví dụ