{"raw_statement":[{"iden":"statement","content":"Elissa is so clever girl, even though her age is 5 years only. Yesterday she spent all the day learning how to count. Currently she is able to solve many complex counting questions, so she decided to invent a new counting problem in order to help preparing this contest.\n\nElissa will give you a string s consisting of digits only (from '_0_' to '_9_'), and your task is to count in how many ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string.\n\nA beautiful sub-string b is a sub-string from string s, such that b contains unique digits only (i.e. each digit from '_0_' to '_9_' can exist at most one time).\n\nElissa thinks that no one can solve this problem because it is very hard. Can you?\n\nThe first line contains an integer n (1 ≤ n ≤ 104), where n is the length of the string s. The second line contains a string s consisting of digits only.\n\nPrint the number of ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. Since the number of ways may be too large, print the answer modulo 109 + 7.\n\nA sub-string of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.\n\nIn the first test case you can divide the given string in 6 ways, which are: \n\n"},{"iden":"input","content":"The first line contains an integer n (1 ≤ n ≤ 104), where n is the length of the string s. The second line contains a string s consisting of digits only."},{"iden":"output","content":"Print the number of ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. Since the number of ways may be too large, print the answer modulo 109 + 7."},{"iden":"examples","content":"Input41213Output6Input512345Output16Input75112516Output28"},{"iden":"note","content":"A sub-string of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.In the first test case you can divide the given string in 6 ways, which are:   1|2|1|3  1|2|13  1|21|3  1|213  12|1|3  12|13  Note that you cannot divide it to (121|3) because the first sub-string contain the digit '_1_' twice."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string $ s \\in \\{0,1,\\dots,9\\}^n $.  \nA *beautiful substring* is a contiguous substring containing only distinct digits.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^4 $  \n2. Each character of $ s $ is a digit from '0' to '9'.  \n\n**Objective**  \nCount the number of ways to partition $ s $ into a sequence of contiguous beautiful substrings.  \nLet $ dp[i] $ denote the number of valid partitions of the prefix $ s[0:i] $ (0-indexed, length $ i $).  \nThen:  \n$$\ndp[0] = 1\n$$\n$$\ndp[i] = \\sum_{\\substack{0 \\leq j < i \\\\ s[j:i] \\text{ is beautiful}}} dp[j] \\quad \\text{for } 1 \\leq i \\leq n\n$$  \nOutput $ dp[n] \\mod (10^9 + 7) $.","simple_statement":"Count the number of ways to split a string of digits into substrings such that each substring has all unique digits.","has_page_source":false}