T1 蛇

\[\texttt{swap(T1, T2);} \]

题目描述

你获得了一个长度为 \(n\) 的字符串 \(a\)，它的每一个位置都印有一个字符 o 或者 x。长期看着一个相同的字符串十分容易产生审美疲劳，所以你决定对它进行一些操作。

你选取了一个参数 \(k\)。则你可以任意次数的对字符串 \(a\) 进行如下两种操作之一（也可以不操作）：

选择一个长度为 \(k\) 的区间 \([l,r]\)。将字符串中第 \(l\) 个到第 \(r\) 个位置（下标从 \(1\) 开始，下同）的字符取反。即 o 变成 x，x 变成 o。
选择一个长度为 \(k\) 的区间 \([l,r]\)。如果字符串中第 \(l\) 个到第 \(r\) 个位置的字符全部是一样的，就可以删除它们，然后剩余字符拼接起来。

为了完全理解第二种操作，这里有一个例子：

字符串 \(a\) 为 oxxoooxox，并且选取了参数 \(k = 3\)。那么可以对区间 \([4,6]\) 进行操作二，因为这个区间的字符全部都是 o。操作完成后，\(a\) 将会变成 oxxxox，这是 oxx 和 xox 拼接的结果。

非常不幸的是，字符串 \(a\) 被污染了。具体来说，某些位置变成了 ?，你不记得这个位置究竟是 o 还是 x 了，所以你认为都是有可能的。

你想要知道，有多少个字符串 \(b\) 可能被 \(a\) 通过上述两种操作表示出来？\(b\) 可以是空串。由于可能的 \(b\) 实在是太多了，所以你只需要输出答案对 \(10^9 + 7\) 取模后的结果。