可怜发现了一种快速构造超长字符串的方法。
最开始，可怜手上有一个空串 $s_0$，接着，可怜对这个串进行了 $n$ 次操作。在第 $i$ 次操作的时候，可怜选择了一个字符 $c$，并利用 $s_{i-1}$ 和 $c$ 构造了字符串 $s_i = cs_{i-1}[1]cs_{i-1}[2] \dots s_{i-1}[m]c$，其中 $m$ 为串 $s_{i-1}$ 的长度。
举例来说，如果 $n=3$ 且可怜选择的字符分别是 $a,b,c$，则 $s_n=cbcacbc$。
现在，可怜想要知道，字符串 $s_n$ 本质不同的非空子序列有多少个。（注意不能为空，但可能是 $s_n$ 本身）。
串 $s$ 是串 $t$ 的子序列当且仅当串 $s$ 可以通过删去 $t$ 中的某些字符得到。
Comet OJ