题目描述

小爱送给了小艾一个迷宫，这个迷宫是一个 $8\times 8$ 的网格图，每个格子上都有一个小写的英文字母。我们定义一个在迷宫上合法的路径为恰好经过了 $n$ 个格子，任意一次移动只移向相邻八联通的格子，且不经过任何重复格子的路径。

为了考验小艾，小爱给出了一个长度为 $n$ 的字符串 $s$，询问网格中有多少条合法的路径，满足路径上的字符连接成的字符串为 $s$。

输入格式

第一行输入一个字符串 s，表示小爱给出的字符串。 接下来 8 行，表示一个 $8\times 8$ 的字符方阵，表示整个迷宫。

输出格式

输出一行一个整数，表示满足条件的合法路径数

aa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa

420

数据范围

对于 $30\%$ 的数据：$1 \leq n \leq 4$ 对于 $60\%$ 的数据：$1 \leq n \leq 8$ 对于 $100\%$ 的数据：$1 \leq n \leq 11$