该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P5170 【模板】类欧几里德算法

题目描述

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

输入格式

第一行给出数据组数 $t$ 。

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

输出格式

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

输入输出样例 #1

输入 #1

2
2 1 0 2
4 3 9 6

输出 #1

1 1 2
11 27 27

说明/提示

本题采用 $\mathrm{Special}\ \mathrm{Judge}$。

答对所有第一问可以获得测试点 $40\%$ 的分数，答对所有第二问、第三问可以分别获得另外 $30\%$ 的分数。

对于所有测试点，有 $1 \leqslant t \leqslant 10^5,\ 0 \leqslant n,\,a,\,b,\,c \leqslant 10^9,\ c \neq 0$ 。