问题描述

给定长度为 $N$ 的字符串 $S$ 和 $T$，它们由小写英文字母组成。

对于字符串 $X$ 和整数 $i$，定义 $f(X,i)$ 为执行以下操作 $i$ 次后得到的字符串：

• 移除 $X$ 的第一个字符，并将该字符追加到 $X$ 的末尾。

找到满足 $0 \le i,j \le N-1$ 的整数对 $(i,j)$ 的数量，使得 $f(S,i)$ 在字典序上小于或等于 $f(T,j)$。

什么是字典序？

简单来说，字典序是词在词典中排列的顺序。我们通过描述一个算法来形式化地定义它，该算法用于找到由小写英文字母组成的两个不同字符串 $S$ 和 $T$ 的顺序。

这里，我们用 $S_i$ 表示字符串 $S$ 的第 $i$ 个字符。同时，如果 $S$ 在字典序上小于 $T$，我们记作 $S < T$，如果 $S$ 在字典序上大于 $T$，我们记作 $S > T$。

1. 设 $L$ 是 $S$ 和 $T$ 长度中的最小值。对于 $i=1,2,\dots,L$，我们检查是否有 $S_i$ 等于 $T_i$。
2. 如果存在 $i$ 使得 $S_i \neq T_i$，设 $j$ 是最小的满足条件的 $i$。比较 $S_j$ 和 $T_j$，如果在字母表顺序中 $S_j$ 小于 $T_j$，则通过确定 $S < T$ 来终止算法，如果不满足这个条件，则通过确定 $S > T$ 来终止算法。
3. 如果不存在满足 $S_i \neq T_i$ 的 $i$，比较 $S$ 和 $T$ 的长度，如果 $S$ 的长度小于 $T$ 的长度，则通过确定 $S < T$ 来终止算法，否则通过确定 $S > T$ 来终止算法。

约束条件

• $1 \le N \le 2 \times 10^5$
• $S$ 和 $T$ 是长度为 $N$ 的字符串，由小写英文字母组成。
• $N$ 是整数。

输入

输入从标准输入中以以下格式给出：

$N$ $S$ $T$

输出

输出结果。

示例输入 1

3
adb
cab

示例输出 1

4

满足条件的 $(i, j)$ 对有 $4$ 个：$(0,0),(0,2),(2,0)$ 和 $(2,2)$。

$(i,j)=(1,2)$ 不满足条件，因为 $f(S,i)=$dba 而 $f(T,j)=$bca。

示例输入 2

10
wsiuhwijsl
pwqoketvun

示例输出 2

56