Заданы четыре натуральных числа \textbf{a}, \textbf{b}, \textbf{c} и \textbf{d}, определяющие следующую рекуррентность: \textbf{x_\{n \}= 1} для \textbf{n} ≤ \textbf{0}, \textbf{x_\{n \}= cx_n_\{-a \}+ dx_n_\{-b\}} для \textbf{n} > \textbf{0}. Для заданного \textbf{n} вычислить \textbf{x_n mod 1000000007}. \InputFile Единственная строка, содержащая пять целых чисел \textbf{a}, \textbf{b}, \textbf{c}, \textbf{d} и \textbf{n }(\textbf{1 }≤ \textbf{a }< \textbf{b }≤ \textbf{2000}, \textbf{1 }≤ \textbf{c}, \textbf{d }≤ \textbf{100}, \textbf{1 }≤ \textbf{n }≤ \textbf{10^9}). \OutputFile Вывести \textbf{x_n mod 1000000007}.