MapGuessing（高级图灵游戏：初始磁带计数）

在“高级图灵游戏”中，你需要编写一个简单图灵机程序来把一段二进制磁带变成目标磁带。

• 目标磁带 goal：长度为 $L$ 的字符串，只包含字符 0 或 1。
• 初始磁带：也是长度为 $L$ 的二进制串（未知）。
• 机器有一个“读写头”，初始时指向磁带中的某一格（你可以选择起始格）。
• 程序由若干命令顺序执行，命令只有四种：
  • 0：把当前格写成 0
  • 1：把当前格写成 1
  • <：读写头左移一格
  • >：读写头右移一格

重要规则： 执行过程中读写头不允许离开磁带（从最左格再左移，或最右格再右移）。只要发生离开磁带，就算失败——哪怕在离开之前磁带曾经等于目标磁带也不算成功。

一个关卡被视为“解决”，当且仅当：

1. 整个程序执行过程中读写头从未离开磁带；
2. 在程序执行的任意时刻（包括开始前、执行中、以及执行完毕后），磁带内容曾经 完全等于 goal。

现在给定 goal 和程序 code（TopCoder 原题是把 code 的多个字符串拼接成一段程序），请你计算：有多少种不同的初始磁带（长度为 $L$ 的二进制串），存在某个起始格，使得上述“解决”条件成立。

输入格式（为便于阅读做了改造）

• 第一行：L goal
  其中 L 是目标字符串长度，goal 是目标字符串。
• 第二行：整数 M，表示程序被分成了 M 段。
• 接下来 M 行：len_i s_i
  其中 len_i 是该段字符串长度，s_i 是该段程序字符串（只含 0/1/</>）。

最终程序等价于把所有 s_i 按顺序直接拼接得到的字符串。

输出格式

输出一行一个整数：可能的初始磁带数量。

36 000000000000000000000000000000000000
1
10 >>>>0>>0>>

59

数据范围（来自原题）

• $1 \le L \le 36$
• $1 \le M \le 15$
• $1 \le len_i \le 37$
• goal 只含 0/1，s_i 只含 0/1/</>。