雾雨魔理沙一直在收集「御灵珠」（Supernatural Beads）。现在她得到了 $n$ 颗御灵珠，并想用它们来施展她的招牌魔法——「极限火花」（Master Spark）。

当她准备施展魔法时，御灵珠会被注入能量。具体来说，每颗御灵珠都会完全随机且独立地获得一个在 $[1, m]$ 范围内的整数作为其能量。注意，当她重复注入能量时，御灵珠的能量可能会发生变化。

经过一些练习，她发现了关于她的御灵珠的一些有趣事实。假设御灵珠的能量分别为 $s_1, s_2, \dots, s_n$，那么魔法的威力为 $\operatorname{lcm}(s_1, s_2, \dots, s_n)$，而魔法的消耗为 $\operatorname{gcd}(s_1, s_2, \dots, s_n)$。这里 $\operatorname{lcm}(s_1, s_2, \dots, s_n)$ 表示整数 $s_1, s_2, \dots, s_n$ 的最小公倍数（LCM），而 $\operatorname{gcd}(s_1, s_2, \dots, s_n)$ 表示整数 $s_1, s_2, \dots, s_n$ 的最大公约数（GCD）。

魔理沙对魔法要求很严格。她设定了两个不大于 $m$ 的正整数 $p$ 和 $q$。她认为一次魔法是成功的，当且仅当魔法的威力不小于 $p$ 且魔法的消耗不大于 $q$。她认为，如果魔法成功，其价值为 $\prod_{i=1}^n s_i$；否则价值为 $0$。

现在她想知道魔法价值的期望值。设答案为 $x$，显然 $x \cdot m^n$ 是一个整数。由于这个数可能很大，你只需要告诉她 $x \cdot m^n \bmod 998244353$ 的值。

输入格式

输入只有一行，包含四个整数 $n, m, p, q$ —— 分别表示御灵珠的数量、御灵珠可能的最大能量，以及定义魔法成功与否的两个参数。

数据范围保证 $1 \le n \le 998244351$ 且 $1 \le p, q \le m \le 2 \times 10^5$。

输出格式

输出只有一行，包含一个在 $[0, 998244353)$ 范围内的整数 —— 魔法价值的期望值，即题面最后一段中的 $x \cdot m^n$ 对 $998244353$ 取模后的值。

样例

输入样例 1

2 4 3 2

输出样例 1

66

输入样例 2

7 2 1 2

输出样例 2

2187

说明

在第一个样例中，共有 $16$ 种可能的情况，成功的状况如下： $\{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 1\}, \{3, 2\}, \{3, 4\}, \{4, 1\}, \{4, 2\}, \{4, 3\}$。

以下情况是不成功的，因为它们的威力小于 $3$： $\{1, 1\}, \{1, 2\}, \{2, 1\}, \{2, 2\}$。

以下情况是不成功的，因为它们的消耗大于 $2$： $\{3, 3\}, \{4, 4\}$。

在第二个样例中，显然所有 $2^7$ 种情况都是成功的。