#agc027e. [agc027_e]ABBreviate

[agc027_e]ABBreviate

给定一个只含小写字母 a,b\mathtt{a}, \mathtt{b} 的字符串 ss,每次你可以执行以下两种操作:

  1. 选取 ss 中连续的两个字符 aa\mathtt{aa},把它们删去,替换成一个字符 b\mathtt{b}
  2. 选取 ss 中连续的两个字符 bb\mathtt{bb},把它们删去,替换成一个字符 a\mathtt{a}

请你求出执行若干次操作后,能够得到的本质不同的字符串有多少个,答案对 (109+7)({10}^9 + 7) 取模。

  • 1s1051 \le |s| \le {10}^5