题目描述

给定四个字符串，每个字符串都只包含小写英文字母 a 到 z，且长度不超过 $50$。

请计算这四个字符串的非空公共子序列有多少种。

这里统计的是不同的子序列字符串的数量，而不是选取下标方案的数量。也就是说，如果同一个字符串可以通过多种不同的下标选择方式得到，它仍然只计算一次。

注意，子序列中的字符不要求在原字符串中连续，只需要保持原有的相对顺序。

输入格式

输入共四行。

第 $i$ 行包含第 $i$ 个字符串。

每个字符串：

• 长度不超过 $50$；
• 仅包含小写英文字母 a 到 z。

输出格式

输出一个整数，表示四个字符串的不同非空公共子序列数量。

答案一定可以用 64 位有符号整数表示。事实上，任意一个长度不超过 $50$ 的字符串至多有 $2^{50}-1$ 个非空子序列下标集合，因此不同公共子序列数量也不会超过该值。

样例

aabb
abab
baba
acba

4

样例说明

四个字符串共有 $4$ 个不同的非空公共子序列：

• a
• b
• aa
• ab

因此答案为 $4$。

数据范围

$1\le |S_i|\le 50$，字符均为小写英文字母。