====== 단어의 개수 ======

===== 풀이 =====
  * [[https://u.acmicpc.net/9034be9c-41f3-4192-a956-49ccfea442d4/2022skku_solution.pdf|에디토리얼]]에서 설명하는 방식은 O(26n)이지만, O(n)으로 풀이가 가능하다.
  * 일반적인 [[ps:tutorial:부분 수열#서로 다른 부분 수열의 개수]] 는 DP를 이용해서 O(n)에 구할 수 있다.
  * 이 점화식에서 S[i]==c 일때 dp값은 이렇게 바뀐다
    * dp[i] = dp[i-1] * 2 - last[c]
    * last[c] = dp[i-1] 이다
  * 그러면 c가 연속으로 k번 나올 때에 어떻게 바뀌는지 규칙을 파악해보면, 다음처럼 바뀌는 것을 확인할수 있다.
    * dp[i] = dp[i-k] * (k+1) - last[c] * k
    * last[c] =  dp[i-k] * k - last[c] * (k-1) 
  * 이제 이대로 구현하면 O(n)에 문제가 해결된다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 24528. 단어의 개수".

- Problem link: https://www.acmicpc.net/problem/24528
- Solution link: http://www.teferi.net/ps/problems/boj/24528

Tags: [DP]
"""

import sys

MOD = 998_244_353


def main():
    N = int(sys.stdin.readline())

    count_by_last_ch = [0] * 26
    tot_count = 1
    for _ in range(N):
        c, v = sys.stdin.readline().split()

        c_ord, v = ord(c) - 97, int(v)
        count_c = count_by_last_ch[c_ord]
        tot_count, count_by_last_ch[c_ord] = (
            (tot_count * (v + 1) - count_c * v) % MOD,
            (tot_count * v - count_c * (v - 1)) % MOD,
        )

    print((tot_count - 1) % MOD)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_4}}