年轻的安娜最近沉迷于手机上的一款填字游戏。填字游戏是一个包含若干空格的单个英文单词。每个空格代表一个需要填入的字母。例如，单词 “programming” 可能以谜题 p_o_rammin_ 的形式出现。在解谜时，安娜首先点击一个空格，然后开始输入字母。一旦安娜输入一个字母，应用程序会自动跳转到下一个空格。当已填入字母的右侧没有更多空格时，应用程序会跳回到单词的开头并从那里继续。安娜会一直输入直到所有空格都被填满。为了解决谜题 p_o_rammin_，安娜可以点击第一个空格并输入 rgg。或者，她也可以点击第二个空格，然后输入 ggr。

来自 Pixabay 的图片

有一天，安娜向你展示了她解决的一个谜题以及她输入的字母序列。你能告诉她所解决的谜题有多少种不同的可能性吗？如果两个谜题的空格位置不同，则它们是不同的。例如，如果谜题单词是 programming 且安娜输入了 rgg，则可能有两种可能的谜题：p_o_rammin_ 和 pro__ammin_。由于答案可能很大，请输出答案对 $1\,000\,000\,007$ 取模的结果。

输入格式

第一行包含一个字符串 $p$，表示谜题单词 ($1 \le |p| \le 10^5$)。第二行包含一个字符串 $s$，表示安娜输入的字母序列 ($1 \le |s| \le \min(50, |p|)$)。两个字符串均仅包含小写英文字母。

输出格式

输出安娜可能解决的不同谜题的数量，对 $1\,000\,000\,007$ 取模。如果安娜不可能通过输入 $s$ 来解决该谜题，则输出零。

样例

输入格式 1

programming
rgg

输出格式 1

2

输入格式 2

aabbaa
aba

输出格式 2

12

输入格式 3

acca
acac

输出格式 3

0