题目背景

"History" 是历史的意思。 但它还有一个很浪漫的解释："Hi, story" —— 你好，故事。

每个字符串背后或许都隐藏着一段不为人知的故事。当我们试图拆解一个冗长的字符串时，是否也能通过不同的组合，寻找到那些散落的片段？

题目描述

给定一个目标字符串 $S$ 和一个包含 $n$ 个不重复字符串的字典集合。求问目标字符串 $S$ 由这 $n$ 个字符串构成的方案数。

注意：字典中的字符串可以重复使用。

输入格式

第一行包含一个字符串 $S$，代表目标字符串。

第二行包含一个整数 $n$，($1 \leq n \leq 7$)，代表字典中字符串的数量。

接下来的 $n$ 行，每行包含一个不重复的字符串，代表字典中的元素。

所有字符串均由小写字母构成，且长度不超过 $20$。

输出格式

一个整数，表示将字符串 $S$ 拆分为字典中字符串的方案总数。

样例

history
2
hi
story

1

ababab
2
ab
abab

3

样例解释

在样例 1 中，字符串 "history" 只能由单词 "hi" 和 "story" 按顺序拼接而成，方案数为 1。

在样例 2 中，字符串 "ababab" 可以由以下三种方式拼接而成：

1. "ab" + "ab" + "ab"
2. "ab" + "abab"
3. "abab" + "ab"