C - 文字列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 2 点

問題文

英小文字からなる 3 個の文字列 S_1, S_2, S_3 が与えられます。
長さ N の英小文字からなる文字列 T であって S_1, S_2, S_3 のいずれも部分列として含まないものの個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 10^3
  • S_1, S_2, S_3 は長さ 10 以下の英小文字からなる空でない文字列
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 S_2 S_3

出力

長さ N の英小文字からなる文字列 T であって S_1, S_2, S_3 のいずれも部分列として含まないものの個数を 998244353 で割った余りを出力せよ。

入力例 1

2
abc de f

出力例 1

624

長さ 2 の英小文字からなる文字列は 676 個あり、そのうち S_2 = de を含む文字列は 1 個、S_3 = f を含む文字列は 51 個で、両者は排反です。よって、676 - 1 - 51 = 624 個が答えとなります。

入力例 2

4
ab ab ab

出力例 2

453125

条件にある「部分列」は「部分文字列」とは異なる点に注意してください。例えば accb は部分列として ab を含んでいるため条件を満たしません。

入力例 3

1000
atcoder algorithm lectures

出力例 3

669410767

Score : 2 points

Problem Statement

You are given three strings S_1, S_2, S_3, each consisting of lowercase English letters.
Find the number of strings T of length N (also consisting of lowercase English letters) such that none of S_1, S_2, S_3 appear as a subsequence of T. Output the answer modulo 998244353.

Constraints

  • 1 \leq N \leq 10^3
  • S_1, S_2, S_3 are non-empty strings of lowercase English letters with length at most 10
  • N is an integer

Input

The input is given from standard input in the following format:

N
S_1 S_2 S_3

Output

Print the number of strings T of length N consisting of lowercase English letters such that none of S_1, S_2, S_3 appear as a subsequence of T, modulo 998244353.

Sample Input 1

2
abc de f

Sample Output 1

624

There are 676 strings of length 2 consisting of lowercase English letters. Among them, 1 string contains S_2 = de, and 51 strings contain S_3 = f. These sets do not overlap. Therefore, the answer is 676 - 1 - 51 = 624.

Sample Input 2

4
ab ab ab

Sample Output 2

453125

Note that subsequence in the condition is different from substring.
For example, accb contains ab as a subsequence, so it does not satisfy the condition.

Sample Input 3

1000
atcoder algorithm lectures

Sample Output 3

669410767