Bacteria

Time limit1sMemory limit1024 MB

Summary

Each adult produces one young per second while young mature into adults; find the total population after T seconds modulo K, given initial counts.

Level: Medium6 of 10
Topics: Math, Combinatorics, Dynamic programming, Number theory
Solved: No attempts yet

Problem

Juku forgot to brush his teeth in the evening, and bacteria began multiplying in his mouth. Each bacterium is either young or adult. Every second, each adult produces one new young bacterium, and a newly born young bacterium becomes an adult during the next second. No bacterium ever dies.

If there are initially $N$ young and $V$ adult bacteria, find how many bacteria (young and adult combined) are in Juku's mouth after $T$ seconds. Instead of the actual count, output the remainder when it is divided by the given number $K$ .

Input

A single line contains four space-separated integers $N$ , $V$ , $T$ , and $K$ ( $0 \le N \le 10^9$ , $0 \le V \le 10^9$ , $0 \le T \le 10^{18}$ , $0 < K \le 10^9$ ).

Output

Output the value $(X \bmod K)$ on a single line, where $X$ is the total number of bacteria in Juku's mouth after $T$ seconds and " $\bmod$ " denotes the remainder of the division.

Examples2

Example 1
Input
```
1 3 2 100
```
Expected output
```
11
```
Example 2
Input
```
0 10 1 20
```
Expected output
```
0
```