Fly high, make it. Get to the new world that I seek. Someday, so I believe. ——

Yuuko 独自居住在 Otoha，一个位于北半球的地方。在那里，她致力于引导青少年，温柔地解开他们困惑的结。在无数次的探寻中，她最终遇到了最后一个问题。在那关键的时刻，Yuu 终于产生了一个深刻的领悟：他一直渴望的女孩依然在那里，耐心地等待着他。

Amamiya Yuuko

给定两个互质的参数 $p, q$，序列 $f(i)$ 由以下公式计算得出：

$$ \begin{cases} f(0) = 0, \\ f(1) = 1, \\ f(i) = p \cdot f(i - 1) + q \cdot f(i - 2) \quad (i \ge 2) \end{cases} $$

Yuuko 想要计算以下求和：

$$ \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{c=1}^{m} \gcd(f(c^a + 1), f(c^b + 1)) $$

由于结果太大，你需要将其对 $1225$ 取模。

输入格式

第一行包含四个整数 $n, m, p, q$ ($1 \le n \le 10^5, 1 \le m, p, q \le 100$)。保证 $\gcd(p, q) = 1$。

输出格式

输出一个整数，表示结果。

样例

样例输入 1

5 5 3 4

样例输出 1

953

样例输入 2

3 3 1 1

样例输出 2

662

样例输入 3

20 10 11 9

样例输出 3

333

说明

Two becomes one, and it through all eternity. Merry Christmas, Yuuko.

Ever Forever