Truy hồi tích luỹ

Điểm: 8,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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

$f_{x} = c^{2 x - 6} \cdot f_{x - 1} \cdot f_{x - 2} \cdot f_{x - 3} với mọi x \geq 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 \leq n \leq 10^{18}$
$1 \leq f_{1}, f_{2}, f_{3}, c \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 1 2 5 3	72900	$f_{4} = 3^{2} \cdot 1 \cdot 2 \cdot 5 = 90$ ; $f_{5} = 3^{4} \cdot 90 \cdot 5 \cdot 2 = 72900$ .
17 97 41 37 11	317451037	$f_{17}$ có giá trị xấp xỉ $2, 28 \times 10^{29587}$ , lấy modulo $10^{9} + 7$ .
4 1 1 1 1	1	$f_{4} = 1^{2} \cdot 1 \cdot 1 \cdot 1 = 1$ .

Bình luận

Không có bình luận tại thời điểm này.