양의 정수 $N$과 $M$이 주어집니다.
각 $k = 1, 2, \dots, N + M - 1$에 대하여, 다음 문제의 답을 $\text{ans}_k$라고 합시다.
각각의 길이가 $N + M - 1$인 두 수열의 쌍 $(a, b)$ (여기서 $a = (a_1, a_2, \dots, a_{N+M-1})$, $b = (b_1, b_2, \dots, b_{N+M-1})$)가 다음 조건을 모두 만족하면 좋은 수열 쌍이라고 부릅니다.
- $(a_1, b_1) = (1, N + 1)$
- $i = 2, 3, \dots, N + M - 1$에 대하여, 다음 중 하나가 성립합니다:
- $(a_i, b_i) = (a_{i-1} + 1, b_{i-1})$
- $(a_i, b_i) = (a_{i-1}, b_{i-1} + 1)$
- $(a_{N+M-1}, b_{N+M-1}) = (N, N + M)$
좋은 수열 쌍 $(a, b)$에 대하여 트리 $T(a, b)$를 다음과 같이 정의합니다.
- $1$부터 $N + M$까지 번호가 매겨진 $N + M$개의 정점을 가진 트리입니다.
- 각 $i = 1, 2, \dots, N + M - 1$에 대하여, 정점 $a_i$와 정점 $b_i$를 잇는 간선이 존재합니다.
트리에 대하여, 정점 $i$와 정점 $j$ 사이의 단순 경로에 있는 간선의 개수를 $\text{dist}(i, j)$라고 합시다. 트리의 점수는 $1 \le i < j \le N + M$과 $\text{dist}(i, j) = k$를 만족하는 정수 쌍 $(i, j)$의 개수로 정의됩니다.
모든 좋은 수열 쌍 $(a, b)$에 대하여 $T(a, b)$의 점수의 합을 $998244353$으로 나눈 나머지를 구하세요.
모든 값 $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$을 계산하고, $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$를 출력하세요. 여기서 $\oplus$는 비트 배타적 논리합(XOR)을 나타냅니다.
입력
입력은 다음 형식으로 주어집니다:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- 모든 입력값은 정수입니다.
출력
정답을 출력하세요.
예제 1
2 2
14
예제 2
24 167
21925979855
예제 3
4297614 4167924
4162418864110099
노트
첫 번째 예제에서 $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$입니다. 따라서 출력해야 하는 값은 $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$입니다.