一个著名的线性递归序列 $f(n)$ 定义如下：
- 对于 $k \le 0$，$f(k) = 1$；
- 对于 $k \ge 1$，$f(k) = a \cdot f(k - p) + b \cdot f(k - q)$。
给定 $n, a, b, p, q$，求 $f(n)$ 对 $119$ 取模的结果。
输入格式
输入的第一行包含 5 个整数 $n, a, b, p, q$ ($1 \le n \le 2 \cdot 10^9, 0 \le a, b \le 2 \cdot 10^9, 1 \le p < q \le 10^4$)。
输出格式
输出 $f(n)$ 对 $119$ 取模的结果。
样例
样例输入 1
1 1 1 1 2
样例输出 1
2
样例输入 2
1000000000 1 2 3 4
样例输出 2
100