Consider a linear function f(x) = Ax + B. Let's define g(0)(x) = x and g(n)(x) = f(g(n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g(n)(x) modulo 109 + 7.

Input

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Output

Print the only integer s — the value g(n)(x) modulo 109 + 7.

Examples

Input

3 4 1 1


Output

7


Input

3 4 2 1


Output

25


Input

3 4 3 1


Output

79
import java.util.Scanner;

public class Main {
    public static void main(String[] str) {
        Scanner reader = new Scanner(System.in);
        long a = reader.nextLong();
        long b = reader.nextLong();
        long n = reader.nextLong();
        long x = reader.nextLong();
        long mod = 1000000007;
        reader.close();

        Matrix matrix = new Matrix(a, b, 0, 1);
        matrix = matrix.exp(n, mod);

        System.out.println((((matrix.a * x) % mod) + matrix.b) % mod);
    }
}

class Matrix {
    long a, b, c, d;

    Matrix(long a, long b, long c, long d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }

    private Matrix multiply(Matrix another) {
        return new Matrix(this.a * another.a + this.b * another.c, this.a * another.b + this.b * another.d,
                this.c * another.a + this.d * another.c, this.c * another.b + this.d * another.d);
    }

    Matrix exp(long power, long mod) {
        if (power == 1)
            return this;

        if (power % 2 == 0) {
            Matrix tmp = this.exp(power / 2, mod);
            tmp = tmp.multiply(tmp);
            return new Matrix(tmp.a % mod, tmp.b % mod, tmp.c % mod, tmp.d % mod);
        }
        else {
            Matrix tmp = this.exp(power - 1, mod);
            tmp = this.multiply(tmp);
            return new Matrix(tmp.a % mod, tmp.b % mod, tmp.c % mod, tmp.d % mod);
        }
    }
}