Simple Recursion

By Kay Akashi

Time: 2000 ms

Memory: 256000 kB

The code judging system is only available during contests. Check out the github repo for test cases and solutions.

Please log in.

Problem Statement

Given a recursion rule $a_{n + 1} = pa_n + q$ , where $a_1 = 1$ , output the value of $a_X$ mod $(10^9 + 7)$ given $X$ .

$1 \leq p, q \leq 3000$ .

$1 \leq X \leq 10^5$ .

$1 \leq X \leq 10^{12}$ .

The first line of input contains $2$ integers, $p$ and $q$ . The second line of input contains $1$ integer, $X$ .

Output a single integer, the value of $a_X$ mod $(10^9 + 7)$ .

3 4
5

$a_1 = 1$ , $a_2 = 3 × 1 + 4 = 7$ , $a_3 = 3 × 7 + 4 = 25$ , $a_4 = 3 × 25 + 4 = 79$ , and $a_5 = 3 × 79 + 4 = 241$ .

2915 2999
965736817718

56311101