Hamed最近发现了一个字符串t，并且突然很喜欢它。他花了几天时间去试着找出他有的其他字符串中的所有子串t。最后他变得疲惫，并且开始思考下面的问题。

对于一个给定的字符串s，有多少种方法去从s中提取出至少一个子串，并使它们互不重叠，且都含有一个子串t？

更形式化地讲，你需要求出有多少对满足下列要求的序列a_1,a_2,...,a_k和b_1,b_2,...,b_k：

k>=1

∀i(1<=i<=k)1<=a_i,b_i<=|s|

∀i(1<=i<=k)b_i>=a_i

∀i(2<=i<=k)a_i>b_(i-1)

∀i(1<=i<=k)t是s_(a_i)s(a_i+1)...s(b_i)的一个子串（字符串s的下标以1开始）

因为答案可能很大，所以输出时应模上10^9+7

//不太会用Markdown，各位大佬不喜勿喷