Counting Repeated Subsequences

We are given a string (s) of length (n) consisting only of the characters from the set ( \Sigma={a,b,c,d,e,f} ). All indices are (1\text{-indexed}).

There are (q) operations; each operation changes exactly one character of (s). For (i=1,2,\dots,q+1), let (s) denote the string after performing the first (i-1) operations (the initial string is when (i=1)).

For each such string, count the number of distinct non-empty subsequences (t) that occur in (s) at least twice (i.e. there exist at least two different index sequences in (s) that form (t)). Since the answer may be very large, output it modulo (998,244,353).

A subsequence is defined as a sequence that can be derived from (s) by deleting zero or more characters without changing the order of the remaining characters. Note that two subsequences are considered the same if their sequence of characters matches, even if they come from different positions in (s).

Note: It is guaranteed that the input sizes are small enough so that a brute-force enumeration of all subsequences is possible.

inputFormat

The first line contains two integers (n) and (q) denoting the length of the string and the number of operations, respectively.

The second line contains the string (s) of length (n) consisting only of characters from ({a,b,c,d,e,f}).

Then (q) lines follow, each containing an integer (pos) and a character (c). This means that the character at position (pos) (1-indexed) in (s) is changed to (c).

After each operation (and the initial string before any operations), you should compute the answer.

outputFormat

Output (q+1) lines. Each line should contain an integer representing the number of distinct non-empty subsequences that occur at least twice in the current string, modulo (998,244,353). The first output corresponds to the initial string, and each subsequent output corresponds to the string after each update.

sample

3 1
aba
2 c

1
1