{"raw_statement":[{"iden":"statement","content":"Arthur is an extremely important person and rarely has the time to talk. To minimize the time spent with words, he developed his own language, which he uses on a daily basis. However, it's very hard to understand whatever comes out of his mouth.\n\nIn order to improve his interaction with the rest of the world, Arthur has asked the Narratives Industrial Complex (CIN in Portuguese) to develop a program which receives a speech S produced by Arthur and a pattern w and prints how many distinct ways we can obtain w by only removing characters from S. Two ways are considered distinct if there is an index 0 ≤ i < |S| such as Si is present in one and not in the other.\n\nSince you are considered the most experienced programmer in CIN, your team has trusted you the task of writing this program.\n\nThe first line consists of a string S(1 ≤ |S| ≤ 105), representing Arthur's speech. S contains only lower and upper case letters.\n\nThe second and last line consists of a string w(1 ≤ |w| ≤ 10), the pattern to be searched.\n\nPrint a single integer: The number of distinct ways to obtain w by removing letters from S. Because this number can be large, print the remained of this number divided by 1000000007 = 109 + 7\n\n"},{"iden":"input","content":"The first line consists of a string S(1 ≤ |S| ≤ 105), representing Arthur's speech. S contains only lower and upper case letters.The second and last line consists of a string w(1 ≤ |w| ≤ 10), the pattern to be searched."},{"iden":"output","content":"Print a single integer: The number of distinct ways to obtain w by removing letters from S. Because this number can be large, print the remained of this number divided by 1000000007 = 109 + 7"},{"iden":"examples","content":"InputweewrshkimsimOutput1InputqqqaaabbbcccfffrrrqabcfrOutput729"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ S \\in \\Sigma^* $ be the input string (speech), where $ \\Sigma $ is the set of alphanumeric characters.  \nLet $ w \\in \\Sigma^* $ be the pattern string, with $ |w| \\leq 10 $.  \n\n**Constraints**  \n1. $ 1 \\leq |S| \\leq 10^5 $  \n2. $ 1 \\leq |w| \\leq 10 $  \n3. All characters in $ S $ and $ w $ are from the set of lowercase and uppercase English letters.  \n\n**Objective**  \nCompute the number of distinct subsequences of $ S $ that are equal to $ w $, modulo $ 10^9 + 7 $.  \n\nThat is, count the number of strictly increasing sequences of indices $ 0 \\leq i_1 < i_2 < \\dots < i_{|w|} < |S| $ such that:  \n$$\nS[i_1]S[i_2]\\dots S[i_{|w|}] = w\n$$  \n\nLet $ dp[j] $ denote the number of ways to match the first $ j $ characters of $ w $ using a prefix of $ S $.  \nWe seek $ dp[|w|] \\mod (10^9 + 7) $.","simple_statement":"Given a string S and a pattern w, count how many distinct ways you can remove characters from S to get w. Two ways are different if the positions of kept characters differ. Return the count modulo 1000000007.","has_page_source":false}