Sum of a geometric sequence

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

Medium5Divide and conquerMathRecursionNo attempts yetTime limit0.5sMemory limit128 MB

Description

Examples2

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}$ .