题目背景

自动机实验室里有一款名为“高级纸带机”的小游戏。

玩家面对一条有限长度的二进制纸带，纸带上的每个格子中都写着 0 或 1。玩家可以选择读写头的初始位置，并让机器依次执行一段程序。程序能够修改纸带上的数字，也能够移动读写头。只要执行过程中纸带曾经与预先给定的目标纸带完全相同，就有机会完成这一关。

小墨鱼刚刚成功完成了一关，却忘记了纸带最初的内容，也忘记了读写头从哪里开始。她只记得目标纸带和自己输入的程序。请你帮助她计算：最初的纸带一共有多少种可能。

题目描述

给定一个长度为 $n$ 的目标二进制串 goal，以及一段长度为 $m$ 的程序 code。

纸带共有 $n$ 个格子，从左到右编号为 $1,2,\ldots,n$。每个格子中存放一个字符 0 或 1。

程序中的每个字符表示一条指令：

• 0：将读写头当前指向的格子改写为 0；
• 1：将读写头当前指向的格子改写为 1；
• <：将读写头向左移动一格；
• >：将读写头向右移动一格。

在执行程序之前，可以任选一个格子作为读写头的初始位置。随后必须按照顺序执行完整段程序。

如果读写头在任意时刻移出了纸带，执行立即失败。即使纸带在此前已经等于目标纸带，这次执行仍然不能算作成功。

若满足以下两个条件，则称某个初始纸带是可能的：

1. 存在一种读写头初始位置，使得执行完整段程序时读写头始终没有离开纸带；
2. 在程序执行过程中的某个时刻，纸带内容恰好等于 goal。

这里的“某个时刻”包括：

• 程序开始执行之前；
• 任意一条指令执行之后；
• 程序全部执行完毕之后。

请计算不同的可能初始纸带数量。

注意：如果同一个初始纸带可以配合多个不同的读写头初始位置成功，它仍然只计算一次。

输入格式

输入共两行。

第一行包含一个二进制串 goal，表示目标纸带。

第二行包含一个字符串 code，表示需要执行的完整程序。

输出格式

输出一个整数，表示可能的初始纸带数量。

样例 1

000
0

4

样例 2

001
0>1

5

样例 3

000
1>1>1

1

样例 4

11001
>><<<<><<

0

样例 5

1000101011
1<<0>>0>1

22

样例 6

00000010000000000000000000000000
><>>0<0<>>1>0><><<0>>0<>><0>0>>><><>>>0<>>0><>>>>0<<><>>0>>>0<0>>0>

13601

样例解释

对于样例 1，共有以下四种可能的初始纸带：

000
001
010
100

例如初始纸带为 100 时，可以让读写头从最左侧格子开始，执行指令 0 后纸带变为目标串 000。

对于样例 3，程序执行过程中会把纸带写成 111，但初始纸带本身可以等于目标纸带。因此只有初始纸带 000 合法。

对于样例 4，虽然初始纸带等于目标纸带时，在程序开始前已经到达目标状态，但无论读写头从哪里开始，完整执行程序时都会越界，因此答案为 $0$。

数据范围

• $1\le n\le 36$；
• $1\le m\le 555$；
• goal 中的每个字符均为 0 或 1；
• code 中的每个字符均为 0、1、< 或 >；
• 答案不超过 $2^{36}$，可以使用 64 位有符号整数保存。