D. Давтагдсан шугаман функц

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$f(x) = Ax + B$ гэсэн шугаман функцийг авч үзье. $n > 0$ бүрийн хувьд $g^{(n)}(x) = f(g^{(n - 1)}(x))$ байх ба $g^{(0)}(x) = x$ гэж тодорхойлье. Өгөгдсөн бүхэл утгууд $A$, $B$, $n$ болон $x$-уудын хувьд $g^{(n)}(x)$-ын утгыг $10^{9} + 7$ модулаар бодож олно уу.

Оролт

Ганц мөрөнд 4 бүхэл тоо $A$, $B$, $n$ болон $x$ ($1 ≤ A, B, x ≤ 10^{9}, 1 ≤ n ≤ 10^{18}$ өгөгдөх ба эдгээр нь бодлогын өгөгдөл доторх параметрүүдийг илэрхийлнэ.

Өгөгдсөн утга $n$ нь хэтэрхий том тоо байж болох учраас та $64$ битийн бүхэл тоон төрлийг уг тоог хадгалахдаа ашиглана уу. C++ дээр та long long гэсэн бүхэл тоон төрлийг Java дээр long гэсэн бүхэл тоон төрлийг ашиглаж болно.

Гаралт

$g^{(n)}(x)$-ын утгыг $10^{9} + 7$ модулаар бодсон утга болох $s$ бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 4 1 1
Гаралт
7
Оролт
3 4 2 1
Гаралт
25
Оролт
3 4 3 1
Гаралт
79
Сэтгэгдлүүдийг ачааллаж байна...