You are given two arrays each with N elements. Elements of each arrays follow a particular generator dependent on factors a,b and c . You have to choose on element from both the arrays such that if you chose i^th element from one array and j^th  element from another array then i should not be equal to j and sum of the both elements should be minimum.
Remember that the generator code is language independent. Please make relevant changes as per the language you use 
A[1] = a*c;
for(i=2 ; i ≤ n ; i++)
{
    A[i] = A[i-1]*a*b*c + A[i-1]*a*b + A[i-1]*a*c;
    A[i] = A[i]%1000000007;
}
B[1] = b*c;
for(i=2 ; i ≤ n ; i++)
{
    B[i] = B[i-1]*b*c*a + B[i-1]*b*a + B[i-1]*b*c;
    B[i] = B[i]%1000000007;
}    

Input
First line contains a ,b and c as input . Next line contains N as input which is the total elements in the arrays
Output
You have to output the minimum sum of the two elements that can be selected from the array with distinct indices
Scoring
2≤ a,b,c,N ≤ 10      20pts
2≤ N ≤ 10^6,2≤ a,b,c ≤ 10^9 40pts
2≤ N ≤ 10^7,2≤ a,b,c ≤ 10^9 40pts

SAMPLE INPUT
1 1 1
3

SAMPLE OUTPUT
4

Explanation

The arrays generated are 1 3 9 and 1 3 9, So answer will be 4
a, b, c = map(int, raw_input().split())
n = int(raw_input())
aa = (a*b*c + a*b + a*c) % 1000000007
bb = (a*b*c + a*b + b*c) % 1000000007
p = a*c
ma1 ,ma2 = p, 1000000007
ia1 = ia2 = 0
q = b*c
mb1 ,mb2 = q, 1000000007
ib1 = ib2 = 0

for i in xrange(1, n):

    C = p * aa % 1000000007
    if C < ma2:
        if C < ma1:
            ma2 = ma1
            ia2 = ia1
            ma1 = C
            ia1 = i
        else:
            ma2 = C
            ia2 = i
    p = C

    D = q * bb % 1000000007
    if D < mb2:
        if D < mb1:
            mb2 = mb1
            ib2 = ib1
            mb1 = D
            ib1 = i
        else:
            mb2 = D
            ib2 = i
    q = D  

if ia1 == ib1:
    print min(ma1+mb2, ma2+mb1)
else:
    print ma1+mb1