Sum of a geometric sequence

Time limit0.5sMemory limit128 MB

Summary

Add the first n terms of a geometric sequence with first term a and ratio r, then print the sum modulo mod.

Level: Medium5 of 10
Topics: Divide and conquer, Math, Recursion
Solved: No attempts yet

Problem

A geometric sequence has first term $a$ and common ratio $r$ . Add its first $n$ terms and find the remainder of that total divided by $\text{mod}$ .

That is, print $a + ar + ar^2 + \cdots + ar^{n-1}$ modulo $\text{mod}$ .

Input

The first line contains $a$ , $r$ , $n$ , and $\text{mod}$ , separated by spaces. All four are natural numbers greater than or equal to $1$ and less than or equal to $10^9$ .

Output

On the first line, print the remainder of the sequence sum divided by $\text{mod}$ .

Examples2

Example 1
Input
```
3 5 2 10
```
Expected output
```
8
```
Example 2
Input
```
1 2 9 100
```
Expected output
```
11
```