{"problem":{"name":"B. So You Think You Can Count?","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10134B"},"statements":[{"statement_type":"Markdown","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## Input\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\n## Output\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\n[samples]\n\n## Note\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.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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10134B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}