题号：NC226684
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
John was reading the local newspaper, and noticed that the phrase “chime a cork teen” could be
split into three sub-phrases “eat”, “more”, and “chicken”. Note that the three sub-phrases
combined contain exactly the same letters as the original phrase and the letters in each sub-phrase
appear in the same order as they appear in the original phrase. Note also that the number of
occurrences of each letter in the three sub-phrases combined is the same as that of the original
phrase.
John began to theorize that the newspapers were sending him messages, but you decide to show
him that a message like that was not abnormal. You want to determine the number of ways a
phrase can be broken down into three words that John finds.
Given three sub-phrases and the original phrase, determine the number of ways the sub-phrases
can be formed from the original phrase. The number of ways can be quite large, so determine the
number modulo 1,000,000,007.
输入描述:
The input consists of four lines. Each of the first three input lines contains 1-100 lowercase letters,
representing a sub-phrase. The fourth input line contains 3-300 lowercase letters, representing the
original phrase. Note that the sum of the lengths of the three sub-phrases is equal to the length of
the original phrase.
输出描述:
Print a single integer representing the number of ways to partition the original phrase into three
groups where each group is one of the three sub-phrases. Print the count modulo 1,000,000,007.
示例1
输入
复制
eat
more
chicken
chimeacorkteen
示例2
输入
复制
the
great
depression
depressigortheneat