Geometric Sum, Large

Difficulty: 1800 4000 ms 128 MB

math

Compute A + A·R + A·R² + … + A·R^N−1 modulo 10⁹+7.

Input: one line with three integers A, R, N.

Output: the sum mod 10⁹+7.

Constraints:

• 1 ≤ A, R ≤ 10¹⁸
• 1 ≤ N ≤ 10¹⁸

Sample Tests

1 2 4

15

3 1 5

15

Read the Editorial