You are given four positive integers \textbf{a}, \textbf{b}, \textbf{c}, and \textbf{d}, which define the following recurrence: \textbf{x_\{n \}= 1} for \textbf{n} ≤ \textbf{0}, \textbf{x_\{n \}= cx_n_\{-a \}+ dx_n_\{-b\}} for \textbf{n} > \textbf{0}. For a given \textbf{n} find \textbf{x_n mod 1000000007}. \InputFile The only line of the input contains five integers \textbf{a}, \textbf{b}, \textbf{c}, \textbf{d}, and \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 Output \textbf{x_n mod 1000000007}.