【模板】类欧几里得算法

题目描述

给定 $n,\,a,\,b,\,c$ ,分别求 $\sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor\,,\ \sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2\,,\ \sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor$ ,答案对 $998244353$ 取模。多组数据。

输入输出格式

输入格式


第一行给出数据组数 $t$ 。 接下来 $t$ 行,每行有四个整数,分别为每组数据的 $n,\ a,\ b,\ c$ 。

输出格式


对于每组数据,输出一行三个整数,为三个答案对 $998244353$ 取模的结果。

输入输出样例

输入样例 #1

2
2 1 0 2
4 3 9 6

输出样例 #1

1 1 2
11 27 27

说明

本题采用 $\mathrm{Special}\ \mathrm{Judge}$。 答对所有第一问可以获得测试点 $40\%$ 的分数,答对所有第二问、第三问可以分别获得另外 $30\%$ 的分数。 ||| |:-:|:-:|:-:| |测试点编号|特殊性质| |$1$|$n,\,a,\,b,\,c\leqslant10$| |$2 \sim 3$|$n,\,a,\,b,\,c\leqslant1000$| |$4$|$n,\,a,\,b,\,c\leqslant10^6$| |$5$|$t=1$| |$6 \sim 10$|无| 对于所有测试点,有 $1 \leqslant t \leqslant 10^5,\ 0 \leqslant n,\,a,\,b,\,c \leqslant 10^9,\ c \neq 0$ 。