trang chủ / bài tập / prodrec

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^{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.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 8,00một phần

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

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loạ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