QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[-7]
统计

给定一个一元二次函数 f(x)=ax2+bx+c。对于满足 1inn 个正整数 i,相应的二次函数值分别为 f(1),f(2),,f(n)。在通常情况下,它们的乘积 ni=1f(i) 不是一个平方数。能整除这个乘积的最大平方数是多少呢?

最大平方数问题:对于给定的一元二次函数 f(x)=ax2+bx+c,计算出能整除 ni=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% 的数据满足 1a,n2×1050b,c2×105