#1482. 圆环之理

圆环之理

题目描述

圆环上等距排列着 nn 个点,我们将任意两个点之间直接连接一条线段,请你给每个点染一个 1a1\sim a 的颜色,每条线段染一个 1b1\sim b 中的颜色,使得这个圆环任意旋转一个不是 2π2\pi 倍数的角度,或者沿任意直线反转,图案都与原先不相同。请你计算这个方案数取模 998244353998244353

本题的 nn 会以一种特殊的方式给出,以保证你能够直接获得它的质因子分解式。

输入格式

第一行输入一个正整数 kk,表示 nn 可以写作 kk 个质数的乘积。

第二行输入 kk 个质数 p1,p2,,pkp_1, p_2, \dots, p_knn 为它们的乘积。

第三行输入两个正整数 a,ba,b,意义如题所示。

输出格式

输出一行一个整数,表示方案数取模 998244353998244353

样例

1
3
2 2
24

rot24.jpeg

数据范围与提示

对于 40%40\% 的数据,n=342n=3\sim 42 各一个测试点,每个测试点占 11 分。

对于 75%75\% 的数据,n1012n\le 10^{12}

对于 100%100\% 的数据,pi109,3n1018,1a,b108p_i \le 10^9, 3\le n\le 10^{18}, 1\le a, b\le 10^8