有一個數列，頭兩個數是 \(0\) 和 \(1\)，接下來的每一個數 \(x_n\)，都是兩個數的和，例如第三個數是 \(0 + 1 = 1\)，第四個數是 \(1 + 1 = 2\)，第五個數是 \(1 + 1 = 2\)。我們知道這個數列是有名的費氏數列。 現在我們仿照費氏數列的生成方式來生成某個數列、該數列的頭兩個數是\( x_1\) 和 \(x_2\)，接下來的每一個數，都是 \(x_n = bx_{n - 1} + ax_{n - 2}\)。給定 \(x_1,  x_2,  a,  b\)，請你寫一個程式計算指定的第 \(n\) 個數 \(x_n\)。

輸入格式

輸入只有一行，有五個正整數，依序為 \(x_1,  x_2,  a,  b,  n(0\leq x_1,  x_2,  a,  b \leq 10^ 9,  3\leq n \leq 10^ 9\)，數值間以空白隔開。

輸出格式

由於 \(x_n\) 的數值可能很大，請輸出 \(x_n\) 除以 \(1000000007\) 的餘數。

範例輸入

["0 1 1 1 5","0 1 1 1 50\r\n\r\n","3 4 5 6 999\r\n\r\n","999999999 999999999 999999999 999999999 999999999"]

範例輸出

["3","778742000","434708377\r\n\r\n","302734374"]

提示

本題出自 2018 TOI Pre (TIOJ 2053)