Kri 非常喜欢字符串，所以他准备找 组字符串研究。
第 次研究中，Kri 准备了两个字符串 和 ，其中 长度为 ，且只由 0, 1, - 三种字符构成（注：这里的第三种字符是减号）， 初始时为空。
每次研究，Zay 会带着一个美丽的长度为 的字符串 来找 Kri 玩，Kri 非常羡慕 Zay 拥有如此美丽的字符串，便也想用字符串 和 变出字符串 。
具体地，Kri 将会进行 次操作。每次操作中，Kri 会取出 的第一个字符（记为 ），并将其从 中删去。如果 ，则 Kri 要删去 的开头字符或结尾字符（数据保证删去后 不为空）。否则，Kri 会将 加入到 的末尾。
当进行完所有操作后，Kri 会检查 是否和 相等。如果 ，Kri 就会感到开心；否则，Kri 会感到难受。
请问在每次研究中，Kri 有多少种操作方式使自己最后感到开心？我们定义两种方案不同，当且仅当在某种方案的某次操作中， Kri 删去了 的开头字符。而在另一种方案的这次操作中， Kri 删去了 的结尾字符。
由于答案可能很大，你只需要输出答案除以 （即 ）的余数。