计算 gcd(x1p1,x2p2,⋯,xnpn)\gcd(x_1^{p_1},x_2^{p_2},\cdots,x_n^{p_n})gcd(x1p1,x2p2,⋯,xnpn) 的值,答案对 109+710^9+7109+7 取模。
输入
第一行一个整数表示 nnn。
第二行 nnn 个整数,第 iii 个数表示 xix_ixi。
第三行 nnn 个整数,第 iii 个数表示 pip_ipi。
1≤n,xi,pi≤1041\leq n,x_i,p_i\leq10^41≤n,xi,pi≤104。
输出
输出一行一个数表示答案。
样例
3 1 1 1 11 45 14
1
2 25 5 1 2
25
提示
数据保证直接输出 111 只能骗到 111 分。
来源
2021 寒假多校(牛客)