Problem Statement

You are given 3 positive integers $A, B, C$ and a positive integer $K$. Initially, the 3 numbers $A, B, C$ are written on a blackboard.

Perform the following operation $K$ times.

• Simultaneously rewrite each of the 3 numbers written on the blackboard with the product of the other 2 numbers.
  

Find the product of the 3 numbers written on the blackboard after the operations are finished, modulo $10^9+7$.

Hint: Fermat's little theorem (opens Wikipedia)

Input

$A\ \ B\ \ C$
$K$

• $1 \leq A, B, C \leq 10^9$
• $1 \leq K \leq 10^{12}$
• All inputs are integers.

Output

Output the value you found, followed by a newline.

Sample

2 3 1
1

36

1 1 1
4879314

1

390421437 291872136 531083427
292874319324

664210506