Hidden Message
시간 제한1초메모리 제한1024 MB
주어진 문자열을 세 개의 부분 수열로 나누어 각각 세 단어가 되게 하는 경우의 수를 1e9+7로 나눈 나머지를 구한다.
문제
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.