$B$를 양의 정수로 이루어진 길이가 $M$인 배열이라고 합시다.
한 번의 연산에서, 대응하는 값 $B_{i_1}, B_{i_2}, \dots, B_{i_k}$가 서로 다른 인덱스의 비어 있지 않은 부분 수열$^\dagger$ $1 \le i_1 < i_2 < \dots < i_k \le M$을 선택한 뒤, 선택한 각 값을 $1$만큼 감소시킬 수 있습니다.
$B$의 점수 $\text{score}(B)$를 $B$의 모든 원소를 $0$으로 만들기 위해 필요한 최소 연산 횟수로 정의합니다.
길이가 $N$인 배열 $A$가 주어집니다.
$A$의 모든 비어 있지 않은 부분 수열에 대한 점수의 합을 구하세요.
값이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하세요.
$^\dagger$ 수열 $C$가 수열 $D$에서 나머지 원소들의 순서를 바꾸지 않고 몇 개의 원소(하나도 삭제하지 않거나 모두 삭제할 수도 있음)를 삭제하여 얻을 수 있다면, 이를 $D$의 부분 수열이라고 부릅니다.
입력
입력은 다음 형식으로 주어집니다:
T N A_1 A_2 ... A_N :
- 모든 입력값은 정수입니다.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- 모든 테스트 케이스에서 $N^2$의 합은 $5000^2$을 초과하지 않음이 보장됩니다.
출력
각 테스트 케이스마다 $A$의 모든 비어 있지 않은 부분 수열에 대한 점수의 합을 $998\,244\,353$으로 나눈 나머지를 하나의 정수로 출력하세요.
예제
예제 입력 1
3 1 5 3 1 1 3 4 2 2 2 2
예제 출력 1
5 16 47
노트
테스트 케이스 1: 유일한 비어 있지 않은 부분 수열은 $[5]$이고, 점수는 $5$입니다. 따라서 답은 $5$입니다.
테스트 케이스 2: $[1, 1, 3]$의 비어 있지 않은 부분 수열은 다음과 같습니다:
- $[1]$과 같은 부분 수열 두 개 (각각 점수 $1$),
- $[3]$ (점수 $3$),
- $[1, 1]$ (점수 $2$),
- $[1, 3]$과 같은 부분 수열 두 개 (각각 점수 $3$),
- $[1, 1, 3]$ (점수 $3$).
따라서 전체 합은 $16$입니다.