{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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_."},{"iden":"output","content":"Print the only integer — the sum of costs of all subsequences of the string _F_(_x_), taken modulo 109 + 7."},{"iden":"examples","content":"Input\n\n2 4\n11\n\nOutput\n\n14\n\nInput\n\n10 100\n1010101010\n\nOutput\n\n553403224"}],"translated_statement":[{"iden":"statement","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] 取模。"},{"iden":"input","content":"第一行包含两个整数 #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_。"},{"iden":"output","content":"输出一个整数——字符串 #cf_span[F(x)] 的所有子序列的代价之和，对 #cf_span[109 + 7] 取模。"},{"iden":"examples","content":"输入\n2 4\n11\n输出\n14\n\n输入\n10 100\n1010101010\n输出\n553403224"}],"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":null,"has_page_source":false}