#44 「 Luv Letter 」

统计

TKD记得在当时,每次收到回信之后,自己都会做一个有趣的统计。

首先,把两封信抽象成两个由小写字母组成的字符串,不妨叫它们字符串A字符串B。

然后,数学很好的TKD就会算出一下四个数量:

在A的子串中,不是B的子串的字符串的数量。

在A的子串中,不是B的子序列的字符串的数量。

在A的子序列中,不是B的子串的字符串的数量。

在A的子序列中,不是B的子序列的字符串的数量。

现在,TKD重新拿出了那些萌萌哒的信件,你能算出TKD曾今统计过的数量吗?

注意了哦~这里说的子串(子序列)是指本质不同的子串(子序列),不同的位置相同的串(序列)也只算一个串(序列)哦~

输入格式

两行,两个小写字母组成的字符串,分别代表A和B。

输出格式

四行,每行一个整数,表示以上4个数量对1000000007($10^9$+7)取模的值。

样例数据

input

aabbcc
abcabc

output

13
5
20
7

样例解释

第一个问题符合的串:

aa, aab, aabb, aabbc, aabbcc, abb, abbc, abbcc, bb, bbc, bbcc, bcc, cc

第二个问题符合的串:

aabb, aabbc, aabbcc, abbcc, bbcc

第三个问题符合的串:

aa, aab, aabb, aabbc, aabbcc, aabc, aabcc, aac, aacc, abb, abbc, abbcc, abcc, ac, acc, bb, bbc, bbcc, bcc, cc

第四个问题符合的串:

aabb, aabbc, aabbcc, aabcc, aacc, abbcc, bbcc

数据规模与约定

A和B的长度都不超过2000。

时间限制:1s

空间限制:512MB

Author: zrt

SAM可视化小工具

[!SAMTOOLS]