Limits 1s, 512 MB

Bolt is working at a prominent company called Icefire. He has been given a task for evaluation. The task is about substring triplets. A string ss of length nn is given at first. To build a substring triplet (s1,s2,s3)(s_1, \, s_2, \, s_3), the following procedures are followed (11-based indexing):

  1. At first, three unique integers b1,b2,b3b_1, \, b_2, \, b_3 (1b1,b2,b3n)(1 \leq b_1, \, b_2, \, b_3 \leq n) are selected

  2. Then an integer pp (1pn; max(b1,b2)+pn+1)(1\leq p\leq n; \space \max(b_1, \, b_2)+p\leq n+1) is chosen such that the following two conditions are satisfied:

    • For each ii (0i<p)(0\leq i < p), sb1+i=sb2+is_{b_1+i} = s_{b_2+i}

    • If max(b1,b2)+pn\max(b_1, \, b_2)+p \leq n, sb1+psb2+ps_{b_1 +p} \neq s_{b_2+p}

    Let, e1e_1 be min(n,b1+p)\min(n, \, b_1+p). The substring s1s_1 is the substring sb1,sb1+1,,se1s_{b_1}, s_{b_1+1}, \dots, s_{e_1}

  3. Similarly, another integer qq (1qn; max(b3,b2)+qn+1)(1\leq q\leq n;\space \max(b_3,b_2)+q\leq n+1) is chosen such that the following two conditions are satisfied:

    • For each ii (0i<q)(0\leq i < q), sb3+i=sb2+is_{b_3+i} = s_{b_2+i}

    • If max(b3,b2)+qn\max(b_3, b_2)+q \leq n, sb3+qsb2+qs_{b_3 +q} \neq s_{b_2+q}

    Let, e3e_3 be min(n,b3+q)\min(n, b_3+q). The substring s3s_3 is the substring sb3,sb3+1,,se3s_{b_3}, s_{b_3+1}, \dots, s_{e_3}

  4. Finally, the substring s2s_2 is generated. Let, e2e_2 be min(n,b2+max(p,q))\min(n, b_2 + \max(p, q)). The substring s2s_2 is the substring sb2,sb2+1,,se2s_{b_2}, s_{b_2+1}, \dots, s_{e_2}

The score of the substring triplet is p×qp\times q.

For example, let a string ss of length n=10n=10 is abababcxya\tt{abababcxya} and b1=3,b2=1,b3=10b_1=3, b_2=1, b_3=10. According to the conditions above, the value of pp will be 44 and so, e1=min(n,b1+p)=min(10,3+4)=7e_1 = \min(n, b_1+p) = \min(10, 3+4) = 7. So, the substring s1=ababcs_1 = \tt{ababc} from abababcxya\tt{ab\underline{ababc}xya}. Similarly, the value of qq will be 11 and so, e3=min(n,b3+q)=min(10,10+1)=10e_3 = \min(n, b_3+q) = \min(10, 10+1) = 10. So, the substring s3=as_3 = \tt{a} from abababcxya\tt{abababcxy\underline{a}}. Finally, the value of e2e_2 will be min(n,b2+max(p,q))=min(10,1+max(4,1))=5\min(n, b_2+\max(p,q)) = \min(10, 1+\max(4,1)) = 5. So, the substring s2=ababas_2 = \tt{ababa} from abababcxya\tt{\underline{ababa}bcxya}. The score of this substring triplet (ababc,ababa,a)(\tt{ababc}, \tt{ababa}, \tt{a}) is p×q=4×1=4p\times q = 4\times 1 = 4.

Icefire tells a substring triplet good if the substrings s1,s2,s3s_1, s_2, s_3 are non-empty and lexicographically s1<s2<s3s_1 < s_2 < s_3 satisfies. Bolt has already generated all possible good substring triplets. Now, he needs to calculate the sum of their scores. Can you calculate it for him?

A substring of a string ss is a string that consists of some consecutive characters from string ss. A string aa is lexicographically smaller than a string bb if either aa is a prefix of bb and aba \neq b, or in the first position where aa and bb differ, the string aa has a letter that appears earlier in the alphabet than the corresponding letter in bb.


The first line contains an integer T (1T105)T\space(1\leq T\leq 10^5) — the number of test cases.

The second line contains an integer n (3n5×105)n\space (3\leq n \leq 5\times 10^5) — the length of the string.

The third line contains the string ss — which consists of only lowercase English letters.

The sum of nn over all test cases will not exceed 5×1055\times 10^5.


In each test case, print a single integer in a line, the sum of the scores of the good substring triplets. As the answer can be very large, print it modulo 998244353998244353.



In the second case, the only good substring triplet is: (za,zza,zzz)\tt(za, zza, zzz). Here, the value of pp and qq are 11 and 22 respectively. So, the answer is = (p×q)mod998244353(p\times q)\mod 998244353 = (1×2)mod998244353(1\times 2)\mod 998244353 = 22.


Login to submit.


90% Solution Ratio
skb_hssnEarliest, Feb '23
Mushfiqur05Fastest, 0.1s
user.2575Lightest, 14 MB
Mushfiqur05Shortest, 2541B
Toph uses cookies. By continuing you agree to our Cookie Policy.