题目描述

定义 $f(i,R,P)$ 为满足 $a^R \times (b^2 + b)^i = b^i \pmod P$ 且 $0 \le a, b \lt P$ 的 $(a,b)$ 数对的个数。

一共有 $Q$ 组询问，每组询问中输入 $R, P, N, K$，要求计算出 $\sum_{i=1}\limits^N i^K \times f(i,R,P) \pmod {998,244,353}$ 的值。

输入格式