You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知，KMP = 烤馍片

题目描述

有一个模式串 $p$ 和一个文本串 $s$ ，请你求出模式串 $p$ 在文本串 $s$ 中出现了多少次。在这道题里，出题人把“出现”的定义改了一下：只要模式串 $p$ 在文本串 $s$ 里从左到右按顺序出现，就算出现了一次。如 abc 在 abcde 里出现了1次，在 abcc 里出现了2次，在 abcbc 里出现了3次。并且出题人把数据范围改的很小： $p$ 的长度 $≤10000$， $s$ 的长度 $≤10000$。现在，你还能求出模式串 $p$ 在文本串 $s$ 中出现了多少次吗？

输入格式

共两行。第1行是模式串 $p$ ，第2行是文本串 $s$

输出格式

一个自然数，表示答案（要 $mod \ 1e9+7$)

样例 #1

样例输入 #1

abc
abcbc

样例输出 #1

3

样例 #2

样例输入 #2

hi
hihihi

样例输出 #2

6

提示

样例2出现的6次分别是：

• 1, 2
• 1, 4
• 1, 6
• 3, 4
• 3, 6
• 5, 6

注意时限800ms，空间限制32MB