{"problem":{"name":"F. Fibonacci String Subsequences","description":{"content":"You are given a binary string _s_ (each character of this string is either _0_ or _1_). Let's denote the cost of string _t_ as the number of occurences of _s_ in _t_. For example, if _s_ is _11_ and ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF946F"},"statements":[{"statement_type":"Markdown","content":"You are given a binary string _s_ (each character of this string is either _0_ or _1_).\n\nLet's denote the cost of string _t_ as the number of occurences of _s_ in _t_. For example, if _s_ is _11_ and _t_ is _111011_, then the cost of _t_ is 3.\n\nLet's also denote the Fibonacci strings sequence as follows:\n\n*   _F_(0) is _0_;\n*   _F_(1) is _1_;\n*   _F_(_i_) = _F_(_i_ - 1) + _F_(_i_ - 2) if _i_ > 1, where  +  means the concatenation of two strings.\n\nYour task is to calculate the sum of costs of all subsequences of the string _F_(_x_). Since answer may be large, calculate it modulo 109 + 7.\n\n## Input\n\nThe first line contains two integers _n_ and _x_ (1 ≤ _n_ ≤ 100, 0 ≤ _x_ ≤ 100) — the length of _s_ and the index of a Fibonacci string you are interested in, respectively.\n\nThe second line contains _s_ — a string consisting of _n_ characters. Each of these characters is either _0_ or _1_.\n\n## Output\n\nPrint the only integer — the sum of costs of all subsequences of the string _F_(_x_), taken modulo 109 + 7.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一个二进制字符串 #cf_span[s]（该字符串的每个字符要么是 _0_，要么是 _1_）。\n\n我们定义字符串 #cf_span[t] 的代价为 #cf_span[s] 在 #cf_span[t] 中出现的次数。例如，如果 #cf_span[s] 是 _11_，而 #cf_span[t] 是 _111011_，那么 #cf_span[t] 的代价为 #cf_span[3]。\n\n我们定义斐波那契字符串序列如下：\n\n你的任务是计算字符串 #cf_span[F(x)] 的所有子序列的代价之和。由于答案可能很大，请对 #cf_span[109 + 7] 取模。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ x ≤ 100]），分别表示 #cf_span[s] 的长度和你感兴趣的斐波那契字符串的索引。\n\n第二行包含 #cf_span[s] —— 一个由 #cf_span[n] 个字符组成的字符串，每个字符要么是 _0_，要么是 _1_。\n\n输出一个整数——字符串 #cf_span[F(x)] 的所有子序列的代价之和，对 #cf_span[109 + 7] 取模。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ x ≤ 100]），分别表示 #cf_span[s] 的长度和你感兴趣的斐波那契字符串的索引。第二行包含 #cf_span[s] —— 一个由 #cf_span[n] 个字符组成的字符串，每个字符要么是 _0_，要么是 _1_。\n\n## Output\n\n输出一个整数——字符串 #cf_span[F(x)] 的所有子序列的代价之和，对 #cf_span[109 + 7] 取模。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\{0,1\\}^n $ be a binary string of length $ n $.  \nLet $ F(x) $ denote the $ x $-th Fibonacci string, defined as:  \n- $ F(0) = \"0\" $,  \n- $ F(1) = \"1\" $,  \n- $ F(x) = F(x-1) + F(x-2) $ for $ x \\geq 2 $,  \nwhere $ + $ denotes string concatenation.  \n\nLet $ \\mathcal{S}(t) $ denote the set of all subsequences of a string $ t $.  \nLet $ \\text{cost}(s, t) = $ number of occurrences of $ s $ as a subsequence in $ t $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100 $  \n2. $ 0 \\leq x \\leq 100 $  \n3. $ s \\in \\{0,1\\}^n $  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{t \\in \\mathcal{S}(F(x))} \\text{cost}(s, t) \\mod (10^9 + 7)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF946F","tags":["combinatorics","dp","matrices"],"sample_group":[["2 4\n11","14"],["10 100\n1010101010","553403224"]],"created_at":"2026-03-03 11:00:39"}}