Sum of Squares in a Recurrence Sequence

Given a sequence \(\{a_n\}\) with initial terms \(a_1\) and \(a_2\). For \(n \ge 3\), the sequence satisfies the recurrence:

\[ a_n = x \times a_{n-1} + y \times a_{n-2} \]

Compute the sum:

\[ S = \sum_{i=1}^{n} a_i^2 \]

Since the answer can be very large, output \(S\) modulo \(10^9+7\).

inputFormat

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

• \(a_1\): the first term of the sequence,
• \(a_2\): the second term of the sequence,
• \(x\): the coefficient for \(a_{n-1}\),
• \(y\): the coefficient for \(a_{n-2}\),
• \(n\): the number of terms in the sequence.

outputFormat

Output a single integer which is the value of \(\sum_{i=1}^{n} a_i^2\) modulo \(10^9+7\).

sample

1 1 1 1 3

6