Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem G: 猜猜这题是不是水题

Problem G: 猜猜这题是不是水题

Time Limit: 3 Sec  Memory Limit: 256 MB
Submit: 9  Solved: 3
[Submit][Status][Web Board]

Description

Fuei又遇到字符串的难题了,因为可能对你来说很简单,所以他向你求助。给出两个非空的字符串S,T。其中每个字符串的长度不超过5000,为简单处理,S,T只可能由小写字母a,b,c组成。先要你从S中选出一个子串X,从T中选出一个子序列Y,使得X与Y相等,问有多少种组合。其中X是S中不同的子串或者Y是T中不同的子序列就是一种不同的组合。PS:子串,子序列傻傻分不清的请自行百度:)

Input

第一行S,第二行T,其中S,T非空,且S,T的长度小于等于5000

Output

输出总共的组合数,因为数字可能很大,请对1e9 + 7取模

Sample Input

aa
aa

Sample Output

5

HINT

[Submit][Status][Web Board]