$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$-ға тең.