24528번 - 단어의 개수

알파벳 소문자로 이루어진 문자열 $S$가 주어진다. 이 문자열 $S$는 매우 길 수 있기 때문에 '압축 문자열'의 형태로 입력이 주어진다. '압축 문자열'은 $(c_i, v_i)$ 형태의 순서 쌍이 여러 개 나열된 형태로 표현된다. 주어진 '압축 문자열'을 문자열 $S$로 복원하는 과정은 다음과 같다.

1. 최초의 문자열 $S$ 는 비어있다.
2. $i=1, 2, \cdots , N$ 에 대하여 차례대로 문자열 $S$의 맨 뒤에 문자 $c_i$를 연속하여 $v_i$ 개 덧붙인다.

예를 들어, $(a,4)$, $(b,3)$, $(c,2)$, $(d,1)$, $(a,1)$ 로 주어진 '압축 문자열'을 복원한 문자열 $S$는 $S=aaaabbbccda$ 이다.

이때, $S$ 의 서로 다른 subsequence 의 개수를 구하여라. 값이 매우 클 수 있으니 998244353으로 나눈 나머지를 출력하도록 한다. subsequence $X$, $Y$가 서로 다르다는 것은, $|X| \ne |Y|$ 이거나, $|X| = |Y|$ 이면서 어떤 $i$에 대해 $X_i \ne{} Y_i$, $1 \le{} i \le{} |X|$가 성립함을 의미한다.

첫째 줄에 문자열 $S$ 의 압축 문자열의 순서쌍 개수를 의미하는 $N (1 \le N \le 1,000,000)$ 이 주어진다.

다음 줄부터 $N$ 줄에 걸쳐 압축 문자열의 $i$번째 순서쌍 $(c_i,v_i)$ 가 차례대로 주어진다. $c_i$ 는 알파벳 소문자이고, $v_i (1 \le v_i \le 10^9)$ 는 개수를 의미한다. 또한 $1<i$ 일 때, $c_{i-1} \ne c_i$ 이다.

서로 다른 subsequence 의 개수를 998244353으로 나눈 나머지를 출력하라.

subsequence 란 주어진 문자열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 문자열을 의미한다.