Grass‐Level Sum over Matching Splitting Sequences

Consider two strings A and B, each consisting only of lowercase letters. For each string of length n, a splitting sequence is defined as a sequence of indices $$0 = p_0 < p_1 < \cdots < p_k < p_{k+1} = n+1,$$ which naturally partitions the string into k+1 parts (called split substrings): the i-th substring is the substring from position \(p_i+1\) to \(p_{i+1}-1\) (possibly empty). Note that all string positions are 1-indexed.

Two splitting sequences (one for A and one for B) are chosen with the same number of chosen interior indices (i.e. the same k). They form a valid interpretation if for every i (with \(1 \le i \le k\)), the characters chosen at positions \(p_i\) in A and \(q_i\) in B are identical, i.e. $$A[p_i] = B[q_i].$$

For a given splitting sequence for A with indices \(0 = p_0, p_1, \ldots, p_k, p_{k+1} = |A|+1\), define its grass‐level as the sum of the t-th powers of the lengths of its split substrings: $$f_A = \sum_{i=0}^{k} (p_{i+1}-p_i-1)^t.$$ Similarly, for B and its splitting sequence, the grass‐level is $$f_B = \sum_{i=0}^{k} (q_{i+1}-q_i-1)^t.$$ An interpretation’s overall grass‐level is f_A+f_B.

Your task is to compute the sum (modulo 998244353) of the overall grass‐levels taken over all possible interpretations of the two strings. Formally, sum over all pairs of splitting sequences (one for A and one for B) that satisfy the condition that they have the same number of chosen positions and, for each corresponding chosen index, the characters match. Note that choosing a splitting sequence for a string is equivalent to choosing an arbitrary subset of positions in \(\{1,2,\ldots, n\}\); the empty subset is allowed. Also, by convention, the empty subset gives a grass‐level of \(|A|^t\) (since there is one gap of length \(|A|\)) and similarly for B.

Input Format: The first line contains an integer t. The second line contains the string A and the third line contains the string B.

Output Format: Output one integer, which is the sum modulo 998244353 of the overall grass‐levels for all possible interpretations.

Note: All formulas above are given in \(\LaTeX\) format.

inputFormat

The input consists of three lines. The first line contains an integer t (the power exponent). The second line contains the string A. The third line contains the string B.

outputFormat

Output a single integer — the sum of overall grass‐levels for all valid interpretations modulo 998244353.

sample

1
ab
ab

8