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
//package com.company;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.in"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.out.println("Memory increased:" + (usedMemoryAfter-usedMemoryBefore) / 1000000 );
//        System.out.println("Time used: " + (TIME_END - TIME_START) + ".");

    }


    public static class Task {
        final int MOD = 1_000_000_007;

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            long A = sc.nextInt();
            long B = sc.nextInt();
            long n = sc.nextLong();
            long x = sc.nextInt();
            if (A != 1) {
                long sol = pow(A, n);
                sol += MOD - 1;
                if (sol >= MOD) sol -= MOD;
                sol *= pow(A - 1, MOD - 2);
                sol %= MOD;
                long mult = (A * x + B - x); mult %= MOD;
                sol *= mult;
                sol %= MOD;
                sol += x;
                if (sol >= MOD) sol -= MOD;
                pw.println(sol);
            } else {
                long sol = x;
                n %= MOD;
                sol += n * B;
                pw.print(sol % MOD);
            }
        }

        public long pow(long a, long b) {
            if (b == 0) return 1;
            if (b % 2 == 0) return pow(a * a % MOD, b >> 1L);
            return a * pow(a * a % MOD, b >> 1L) % MOD;
        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public Scanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}
