题目描述
小爱送给了小艾一个迷宫，这个迷宫是一个 $8\times 8$ 的网格图，每个格子上都有一个小写的英文字母。我们定义一个在迷宫上合法的路径为恰好经过了 $n$ 个格子，任意一次移动只移向相邻八联通的格子，且不经过任何重复格子的路径。
为了考验小艾，小爱给出了一个长度为 $n$ 的字符串 $s$，询问网格中有多少条合法的路径，满足路径上的字符连接成的字符串为 $s$。
输入
第一行输入一个字符串 s，表示小爱给出的字符串。
接下来 8 行，表示一个 $8\times 8$ 的字符方阵，表示整个迷宫。
输出
输出一行一个整数，表示满足条件的合法路径数
样例输入输出
输入#1
复制
aa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
提示
对于 $30\%$ 的数据：$1 \leq n \leq 4$
对于 $60\%$ 的数据：$1 \leq n \leq 8$
对于 $100\%$ 的数据：$1 \leq n \leq 11$