実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 1800 点
問題文
互いに区別のできない 3 つの石が、数直線上の座標が整数の点に置かれています。これらの石に対して次の操作を考えます:
- 3 つの石を、その時点で座標の小さい方から順に(同じ位置にある石については適当な順に) A, B, C とする。次のいずれかを行う。
- A を B に関して対称な位置に移動する。
- C を B に関して対称な位置に移動する。
はじめに 3 つの石が置かれている座標 a, b, c が与えられます。操作を何度でも行える(0 回でもよい)とき、操作結果の 3 つの石の座標の組合せとしてありうるものの個数を 998244353 で割った余りを求めてください。
石が互いに区別できないことに注意してください。より厳密にいえば、3 つの石の座標の組合せを多重集合として数え上げてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T\leq 10^5
- -10^{18}\leq a\leq b\leq c\leq 10^{18}
入力
入力は以下の形式で標準入力から与えられます。
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます。
a b c
出力
T 行出力してください。i 行目には、\text{case}_i に対する答えを出力してください。
入力例 1
6 1 3 5 -2 -2 5 0 1 3 31 41 59 -123456789 0 987654321 -1000000000000000000 0 1000000000000000000
出力例 1
5 2 9 70 182333351 5
(a,b,c) = (1,3,5) である場合、操作結果の 3 つの石の座標の組合せとしてありうるのは次の 5 通りです:
- (1,3,5), (1,1,3), (-1,1,1), (3,5,5), (5,5,7)
次の図も参考にしてください。
Score : 1800 points
Problem Statement
There are three indistinguishable stones at integer coordinates on a number line. Consider the following operation on these stones:
- Let A, B, C be the three stones in ascending order of coordinate (ties broken arbitrarily). Perform one of the following.
- Move A to the symmetric position with respect to B.
- Move C to the symmetric position with respect to B.
You are given the initial coordinates a, b, c of the three stones. Find the number, modulo 998244353, of possible combinations of coordinates of the three stones after zero or more operations.
Note that the stones are indistinguishable. More strictly speaking, count the possible multisets of coordinates of the three stones.
We will give you T test cases; solve each of them.
Constraints
- 1\leq T\leq 10^5
- -10^{18}\leq a\leq b\leq c\leq 10^{18}
Input
Input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each case is in the following format:
a b c
Output
Print T lines. The i-th line should contain the answer for \text{case}_i.
Sample Input 1
6 1 3 5 -2 -2 5 0 1 3 31 41 59 -123456789 0 987654321 -1000000000000000000 0 1000000000000000000
Sample Output 1
5 2 9 70 182333351 5
For (a,b,c) = (1,3,5), the five possible combinations of the three stones after operations are:
- (1,3,5), (1,1,3), (-1,1,1), (3,5,5), (5,5,7).
The figure below may be helpful.