問題文
鳗鱼正在玩鼓游戏。太鼓游戏是一种根据屏幕上显示的琴弦敲击鼓的游戏。显示的字符串是 S ,敲击鼓的中心, 如果T ,则敲击鼓的边缘。在这个游戏中一些字符串 字符串中会显示 1 ,根据这些字符串按正确的顺序敲击鼓即可通关。然而,屏幕上显示的字符串之间的间距非常窄,以至于很难分辨字符串是在哪里分开的。
完成游戏后,Unagi 决定计算屏幕上显示的字符串中正确分隔符的数量。然而,正确的定界方法是定界字符串的方法,这样字符串的每个定界部分都是一个字符串。 S 或字符串 指与 T 匹配的内容。
入力
输入是按以下格式从标准输入给出的。
X S T
- 1 行包含屏幕上显示的字符串。 给出了 X (1 ≦ |X| ≦ 1000) 。然而,|X| 是一个字符串 让它代表 X 的长度。
- 2 行包含一个字符串,指示您敲击鼓的中心。 S (1 ≦ |S| ≦ |X|) 。 表示
- 3 线是一条字符串,指示您敲击鼓的边缘。 T (1 ≦ |T| ≦ |X|, S \neq T) 。 表示
- 所有输入字符串必须为小写字母 (
仅
a-z)。 - 分隔屏幕上显示的字符串的正确方法是什么? 1 保证有多个。
出力
计算屏幕上显示的字符串的正确分隔符的数量。 除以 1,000,000,007 (10^9+7) 后的余数 1 行上输出。另外,在输出末尾添加换行符。 您可以像
入力例1
dondonkatsudon don katsu
出力例1
1
don,don,katsu,don 一样将它们分开。
此外,没有其他正确的方法来分离它们。 如何分开
入力例2
aaaaa aaa aa
出力例2
2
aaa,aa 和 如何像aa,aaa 一样分开 2 街道存在。
入力例3
ffffffffffffffffffffffffffffffffffffffffffffffffffffffff f ff
出力例2
435293607
答案可能非常大,所以 除以1,000,000,007 时不要忘记求余数。