有一个由0/1组成的字符串 sss 初始是空，你对它进行了 nnn 次操作，一共有三种可供选择的操作，分别是：
显然，一共有 3n3^n3n 种可能的操作序列，恋恋想知道，其中有多少种序列，使得最后得到的字符串 sss 为她想要的 TTT ,答案对 109+710^9+7109+7 取模输出.
第一行一个正整数 nnn.
第二行一个零一字符串 TTT.
一行一个非负整数表示答案取模后的结果.
3 0
5
298 1010101010100
702160232
4000 101010100101010101010101010010000010101011111100101
492748191
1≤n≤50001\leq n\leq50001≤n≤5000
1≤∣S∣≤n1\leq |S|\leq n1≤∣S∣≤n