I. If SSP-SP was longer
time limit per test
0.5 с
memory limit per test
256 megabytes
input
standard input
output
standard output

Betinho was born in the state of São Paulo and while he was looking at his ID, he noticed that the issuing authority of the document was SSP-SP (Public Security department of São Paulo). He found the name quite curious because if you concatenate the abbreviation of the state of São Paulo "SP" with itself and add an "S" in front (to its left), the result is "SSPSP", which is the same as the name of the issuing authority. In the same way, it is possible to invent a sequence of increasingly larger names by following the same process, where the next term is equal to the previous one concatenated with itself plus an "S" in front. Thus, the first terms of the sequence are as follows:

$$$s_1$$$ = SP
$$$s_2$$$ = SSPSP
$$$s_3$$$ = SSSPSPSSPSP
$$$s_4$$$ = SSSSPSPSSPSPSSSPSPSSPSP
$$$s_5$$$ = SSSSSPSPSSPSPSSSPSPSSPSPSSSSPSPSSPSPSSSPSPSSPSP
$$$...$$$

Betinho is very curious about this sequence and came up with a challenge. Betinho will write a string $$$A$$$ made up only of the letters 'S' and 'P' and will also create string $$$B$$$ formed by the concatenation of $$$N$$$ terms of this sequence. You must calculate how many intervals of string $$$B$$$ are also substrings of string $$$A$$$. More formally, you need to calculate the number of distinct pairs $$$(i,j)$$$ such that the string formed by the characters of $$$B$$$ from position $$$i$$$ to $$$j$$$ is a substring of string $$$A$$$.

For example, if $$$A$$$ = "PSP" and $$$B = S_2 + S_1 =$$$ "SSPSPSP", in this case, the answer is $$$14$$$ because $$$A$$$ has $$$5$$$ distinct substrings ("P", "S", "PS", "SP", "PSP") and these substrings can be found in $$$14$$$ different intervals of string $$$B$$$:

$$$(1,1) →$$$ |S|SPSPSP$$$(3,5) →$$$ SS|PSP|SP$$$(5,7) →$$$ SSPS|PSP|
$$$(2,2) →$$$ S|S|PSPSP$$$(4,4) →$$$ SSP|S|PSP$$$(6,6) →$$$ SSPSP|S|P
$$$(2,3) →$$$ S|SP|SPSP$$$(4,5) →$$$ SSP|SP|SP$$$(6,7) →$$$ SSPSP|SP|
$$$(3,3) →$$$ SS|P|SPSP$$$(5,5) →$$$ SSPS|P|SP$$$(7,7) →$$$ SSPSPS|P|
$$$(3,4) →$$$ SS|PS|PSP$$$(5,6) →$$$ SSPS|PS|P

Betinho needs your help now to solve this challenge. Since the answer can be very large, print the answer modulo $$$998244353$$$.

Input

The input consists of $$$3$$$ lines. The first line contains the string $$$A$$$ of up to $$$1000$$$ letters made up only of characters 'S' and 'P'. The second line contains the integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ equal to the number of terms of the sequence that will be concatenated to form string $$$B$$$. The third line contains $$$N$$$ integers $$$T_i$$$ $$$(1 \le T_i \le 1000)$$$ indicating the terms of the sequence that should be concatenated to form string $$$B$$$.

Output

The output should contain only one line with the number of intervals of string $$$B$$$ that are substrings of string $$$A$$$ modulo $$$998244353$$$.

Examples
Input
PSP
2
2 1
Output
14
Input
SSS
1
3
Output
11
Input
S
5
1 2 3 4 5
Output
57