给定一个一元二次函数 f(x)=ax2+bx+c。对于满足 1≤i≤n 的 n 个正整数 i,相应的二次函数值分别为 f(1),f(2),⋯,f(n)。在通常情况下,它们的乘积 n∏i=1f(i) 不是一个平方数。能整除这个乘积的最大平方数是多少呢?
最大平方数问题:对于给定的一元二次函数 f(x)=ax2+bx+c,计算出能整除 n∏i=1f(i) 的最大平方数。
输入格式
输入的第一行有四个整数 a,b,c,n,,分别表示给定的一元二次函数 f(x)=ax2+bx+c 的相应系数为 a,b,c,以及乘积的项数为 n。
输出格式
输出能整除 ∏ni=1f(i) 的最大平方数,对 998244353 取模的结果。
样例数据
样例输入
1 2 3 4
样例输出
2916
子任务
测试数据中 100% 的数据满足 1≤a,n≤2×105,0≤b,c≤2×105 。