Summoning Spell Comparison

Summoning Spell is a core magic of the cemetery faction. A hero possessing this magic gains a number of skeletons after a battle depending on the number of enemies eliminated. The effect of a summoning spell with parameters \(A\) and \(B\) is defined as follows:

\(F_{A,B}(1)=A, \quad F_{A,B}(2)=B, \quad \text{and for } x\ge3,\quad F_{A,B}(x)=\lfloor \sqrt{F_{A,B}(x-2)\cdot F_{A,B}(x-1)}\rfloor+1.\)

Two heroes possess summoning spells with different attributes. Hero \(\alpha\) has attributes \(A\) and \(B\) while hero \(\beta\) has attributes \(X\) and \(Y\). To compare their summoning capabilities, compute the following expression:

\[ \prod_{i=1}^{n}\Bigl( F_{X,Y}(i)-F_{A,B}(i) \Bigr). \]

Note: \(\lfloor x \rfloor\) denotes the floor function, i.e. the greatest integer less than or equal to \(x\).

inputFormat

The input consists of a single line with five space-separated integers:

\(A\), \(B\), \(X\), \(Y\), and \(n\).

outputFormat

Output a single integer representing the computed product:

\[ \prod_{i=1}^{n}\Bigl( F_{X,Y}(i)-F_{A,B}(i) \Bigr) \]

sample

1 2 2 3 3

1