P4199 万径人踪灭

保先生是个好司机，总是开车带学生们上山玩。但是保先生去年开了最后一趟车后，由于一些奇奇怪怪的原因转行了。半年间，再也没有从这条路上山的人了。 当 VFleaKing 再次来到这座山玩的时候，发现已经没有往日的来来往往的游人了。算了，过去保先生还在的时候，来山上玩的人，也不全是来欣赏山上的风景的。

如果机房马上要关门了，或者你急着要走，请直接跳到第六个自然段。 VFleaKing 注意到了这条上山下山的土路，有些地方能欣赏到美景，有些地方则不能。把上山的道路每 $10$ cm 分为一小段，则对于每一小段，用 `a` 表示能欣赏到美景，用 `b` 表示不能欣赏到美景，就能得到一个只含 `a`、`b` 的字符串 $s$。当然由于下山和上山是一条路，所以下山的道路的字符串就是将上山的道路的字符串反过来。 设上山字符串长度为 $n$，每个字符依次为 $s_1, s_2 .…, s_n$。在上山和下山的路上，VFleaKing 会选择某些小段查看旁边的景色，其他时间低头走路。即 VFleaKing 会选择 $k$ 个小段 $x_1, x_2 …x_k$，且 $k >0$，$1\le x_1

无

无

## 样例解释 ### 样例解释 1 $14$ 个方案分别是： - $[1,3]$，$[1,4]$，$[2,5]$，$[1,6]$，$[3,6]$，$[4,6]$，$[1,7]$，$[3,7]$，$[4,7]$； - $[1,4,7]$，$[3,5,7]$； - $[1,3,4,6]$，$[1,2,5,6]$，$[3,4,6,7]$。 ### 样例解释 2 我已经想到了一个绝妙的解释，可惜方案太多，写不下了。 ### 样例解释 3 我已经想到了一个绝妙的解释，可惜方案太多，写不下了。 ## 数据范围 - 其中 $10\%$ 的数据，字符串仅包含字母 `a` 或字母 `b`。 - 另有 $20\%$ 的数据，$n\le 1000$。 - 另有 $20\%$ 的数据，要么 `a` 的个数不超过 $10$，要么 `a` 的个数不超过 $10$。 - 另有 $10\%$ 的数据，$n\le 10000$。 - 对于 $100\%$ 的数据，$n \le 100000$。 ## 来源 - 2013 湖北互测 week1 - bzoj 3160 - 信息学奥赛之数学一本通 - stong9070 整理