Iterated Linear Function

Submit solution
Points: 100
Time limit: 2.0s
Memory limit: 64M
Author:
carlgauss
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Consider a linear function \(f(x) = Ax + B\). Let's define \(g^{(0)}(x) = x\) and \(g^{(n)}(x) = f(g^{(n - 1)}(x))\) for \(n > 0\). For the given integer values A, B, n and x find the value of g^{(n)}(x) modulo \(10^9 + 7\).

Input Specification

One line whit T number of test cases Each of T lines contains four integers A, B, n and \(x (1 \le A, B, x \le 10^9, 1 \le n \le 10^{18})\) — the parameters from the problem statement.

Output Specification

Print one integer s per line — the value g^{(n)}(x) modulo \(10^9 + 7\).

Sample input 1

3
3 4 1 1
3 4 2 1
3 4 3 1

Sample output 1

7
25
79

Comments


  • 1
    sz02  commented on July 12, 2021, 8:03 p.m.

    Ya ahora sí da accepted, gracias


  • 3
    sz02  commented on July 12, 2021, 3:48 a.m.

    Tengo una solución AC de este exx en codeforces, la unica diferencia es que en el CF la entrada no es por casos de prueba. Mi solución trabaja en log(N) y eso debe pinchar. Me gustaría q comprobaran los juegos de datos. Hay un solo envío accepted q es el del q puso el problema. De no haber error disculpen las molestias.


    • 4
      aniervs  commented on July 12, 2021, 7:49 p.m.

      Ya se arregló. Gracias por avisar.