Number of Words

You are given a string $S$ consisting of lowercase English letters. Because $S$ can be extremely long, it is given in the form of a 'compressed string'. A 'compressed string' is expressed as a sequence of ordered pairs of the form $(c_i, v_i)$. The process of restoring the given 'compressed string' to the string $S$ is as follows.

1. The initial string $S$ is empty.
2. For $i=1, 2, \cdots, N$, append the character $c_i$ repeated $v_i$ times to the end of the string $S$, in order.

For example, the string $S$ restored from the 'compressed string' given as $(a,4)$, $(b,3)$, $(c,2)$, $(d,1)$, $(a,1)$ is $S=aaaabbbccda$.

Find the number of distinct subsequences of $S$. The value can be very large, so output it modulo 998244353. Subsequences $X$ and $Y$ are different if $|X| \ne |Y|$, or if $|X| = |Y|$ and $X_i \ne{} Y_i$ for some $i$ with $1 \le{} i \le{} |X|$.

The first line gives $N (1 \le N \le 1,000,000)$, the number of ordered pairs in the compressed string of $S$.

The next $N$ lines give the $i$-th ordered pair $(c_i,v_i)$ of the compressed string, in order. $c_i$ is a lowercase English letter, and $v_i (1 \le v_i \le 10^9)$ is the count. Also, when $1<i$, $c_{i-1} \ne c_i$.

Output the number of distinct subsequences modulo 998244353.

A subsequence is a string obtained by listing some positions of the given string in their original order.