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] = ac;
for(i=2 ; i ≤ n ; i++)
{
A[i] = A[i-1]abc + A[i-1]ab + A[i-1]ac;
A[i] = A[i]%1000000007;
}
B[1] = bc;
for(i=2 ; i ≤ n ; i++)
{
B[i] = B[i-1]bca + B[i-1]ba + B[i-1]bc;
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

见题面

见题面