← 返回题目列表

AtCoder · code_thanks_festival_14_qualb_f

F. 太鼓游戏

中文机器翻译题面 查看原题

問題文

鳗鱼正在玩鼓游戏。太鼓游戏是一种根据屏幕上显示的琴弦敲击鼓的游戏。显示的字符串是 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 时不要忘记求余数。