P7469 [NOI Online 2021 提高组] 积木小赛

Alice 和 Bob 最近热衷于玩一个游戏——积木小赛。 Alice 和 Bob 初始时各有 $n$ 块积木从左至右排成一排，每块积木都被标上了一个英文小写字母。 Alice 可以从自己的积木中丢掉任意多块（也可以不丢）；Bob 可以从自己的积木中丢掉最左边的一段连续的积木和最右边的一段连续的积木（也可以有一边不丢或者两边都不丢）。两人都不能丢掉自己所有的积木。然后 Alice 和 Bob 会分别将自己剩下的积木按原来的顺序重新排成一排。 Alice 和 Bob 都忙着去玩游戏了，于是想请你帮他们算一下，有多少种不同的情况下他们最后剩下的两排积木是相同的。 两排积木相同，当且仅当这两排积木块数相同且每一个位置上的字母都对应相同。 两种情况不同，当且仅当 Alice（或者 Bob）剩下的积木在两种情况中不同。

无

无

对于所有测试点：$1\le n \le 3000$，$s$ 与 $t$ 中只包含英文小写字母。 测试点 $1$ 满足：$n\le3000$，$s$ 与 $t$ 中只包含同一种字母。 测试点 $2,3,4$ 满足：$n\le100$。 测试点 $5,6,7$ 满足：$n\le500$。 测试点 $8,9,10$ 满足：$n\le3000$。 感谢 [w33z8kqrqk8zzzx33](https://www.luogu.com.cn/user/220037) 提供测试数据。