Besides data structures and number theory, ZYB also loves strings. Considera stringS{S}Sof lengthn{n}n, denoteSiS_iSias thei{i}i-th character in the string . Define a string functionfffsuch that∣f∣=yx+1{|f|=y-x+1}∣f∣=yx+1and thek{k}k-th character off{f}fismaxi=x…x+k1Si. For example, ifS=dbca{S=dbca}S=dbca, thenf=dddd,f=bcc{f} = dddd, f = bccf=dddd,f=bcc. LetA={f∣1≤x1≤x2≤y2≤y1≤n}{A={f mid 1 leq x_1 leq x_2 leq y_2 leq y_1 leq n}}A={f∣1≤x1≤x2≤y2≤y1≤n}. ZYB wants to know how many different strings in setA{A}A.
Besides data structures and number theory, ZYB also loves strings. Consider a string S{S}S of length n{n}n, denote SiS_iSi as the i{i}i-th character in the string (1-based). Define a string function f(S,x,y)(1≤x≤y≤n)f(S, x, y)(1 leq x leq y leq n)f(S,x,y)(1≤x≤y≤n) such that ∣f(S,x,y)∣=y−x+1{|f(S, x, y)|=y-x+1}∣f(S,x,y)∣=y−x+1 and the k{k}k-th character of f(S,x,y){f(S, x, y)}f(S,x,y) is maxi=x…x+k−1Simax_{i=x dots x+k-1} S_imaxi=x…x+k−1Si. For example, if S=dbca{S=dbca}S=dbca, then f(S,1,4)=dddd,f(S,2,4)=bcc{f(S, 1, 4)} = dddd, f(S, 2, 4) = bccf(S,1,4)=dddd,f(S,2,4)=bcc. Let A={f(f(S,x1,y1),x2−x1+1,y2−x1+1)∣1≤x1≤x2≤y2≤y1≤n}{A={f(f(S,x_1,y_1), x_2-x_1+1,y_2-x_1+1) mid 1 leq x_1 leq x_2 leq y_2 leq y_1 leq n}}A={f(f(S,x1,y1),x2−x1+1,y2−x1+1)∣1≤x1≤x2≤y2≤y1≤n}. ZYB wants to know how many different strings in set A{A}A (i.e. the value of ∣A∣{|A|}∣A∣).
