OIer博客

Alice 和 Bob 最近热衷于玩一个游戏——积木小赛。

Alice 和 Bob 初始时各有 $n$ 块积木从左至右排成一排，每块积木都被标上了一个英文小写字母。

Alice 可以从自己的积木中丢掉任意多块（也可以不丢）；Bob 可以从自己的积木中丢掉最左边的一段连续的积木和最右边的一段连续的积木（也可以有一边不丢或者两边都不丢）。两人都不能丢掉自己所有的积木。然后 Alice 和 Bob 会分别将自己剩下的积木按原来的顺序重新排成一排。

Alice 和 Bob 都忙着去玩游戏了，于是想请你帮他们算一下，有多少种不同的情况下他们最后剩下的两排积木是相同的。

两排积木相同，当且仅当这两排积木块数相同且每一个位置上的字母都对应相同。

两种情况不同，当且仅当 Alice（或者 Bob）剩下的积木在两种情况中不同。

第一行一个正整数 $n$，表示积木的块数。

第二行一个长度为 $n$ 的小写字母串 $s$，表示 Alice 初始的那一排积木，其中第 $i$ 个字母 si​ 表示第 $i$ 块积木上的字母。

第三行一个长度为 $n$ 的小写字母串 $t$，表示 Bob 初始的那一排积木，其中第 $i$ 个字母 ti​ 表示第 $i$ 块积木上的字母。

一行一个非负整数表示答案。

对于所有测试点：$1\le n\le 3000$，$s$ 与 $t$ 中只包含英文小写字母。

测试点 $1$ 满足：$n\le 3000$，$s$ 与 $t$ 中只包含同一种字母。

测试点 $2,3,4$ 满足：$n\le 100$。

测试点 $5,6,7$ 满足：$n\le 500$。

测试点 $8,9,10$ 满足：$n\le 3000$。