G. Spell Trick
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Frieren wants to learn a new spell. Unfortunately, the spell is hidden in a grimoire that has an interesting lock on it. To help unlock the lock, help Frieren solve this problem!

The function $$$f(x, y)$$$ is defined below.

int f(int x, int y) {
  int ans = 0;
  while (x != 0 and y != 0) {
    int g = gcd(x, y);
    x -= g;
    y -= g;
    ans++;
  }
  return ans;
}

Calculate $$$$$$\sum_{i = 0}^{d} f(a + i, a + p^x + i)$$$$$$ where $$$p$$$ is a prime. Since the answer could be large print it modulo $$$10^9 + 7$$$.

Input

The first line will contain four positive integers $$$a$$$, $$$p$$$, $$$x$$$, and $$$d$$$. Note that it is guaranteed that $$$p$$$ will be a prime.

$$$1 \le a \le a + p^x + d \le 10^{18}$$$.

Output

Print a single integer representing the answer.

Examples
Input
2 2 3 8
Output
16
Input
10 7 2 100
Output
678