{"raw_statement":[{"iden":"statement","content":"Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants n tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are 2s1, 2s2, ..., 2sn. He can only buy a lot of tiles sized m × m, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?\n\nThe first line of the input gives the number of test cases: t (1 ≤ t ≤ 1000). t lines follow. Each line start with the number n (1 ≤ n ≤ 500) and m (1 ≤ m ≤ 231 - 1), indicating the number of required tiles and the size of the big tiles Enzo can buy. n numbers follow: s1, s2, ..., sn (1 ≤ 2sk ≤ m), showing the sizes of the required tiles.\n\nFor each test case, output one line containing the number of the big tiles Enzo need to buy.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases: t (1 ≤ t ≤ 1000). t lines follow. Each line start with the number n (1 ≤ n ≤ 500) and m (1 ≤ m ≤ 231 - 1), indicating the number of required tiles and the size of the big tiles Enzo can buy. n numbers follow: s1, s2, ..., sn (1 ≤ 2sk ≤ m), showing the sizes of the required tiles."},{"iden":"output","content":"For each test case, output one line containing the number of the big tiles Enzo need to buy."}],"translated_statement":[{"iden":"statement","content":"Michael 的机器人被困在一个迷宫中！迷宫是一个 $n \\times m$ 的矩形网格，其中有一些机器人无法通过的障碍物。最初，机器人位于迷宫的 $(1, 1)$ 位置。幸运的是，他可以使用一个长度为 $K$ 的字符串 $S$ 来指挥机器人。在第 $i$ 次移动时，\n\n然而，他的机器人未能接收到所有的指令！在机器人接收到的字符串 $S$ 中，如果 $S_i$ 是一个 \"?\"，机器人就不知道确切的指令。请计算机器人遵循指令而不撞到障碍物或离开迷宫的方案数。由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果。\n\n第一行包含三个整数 $n, m, K$ $(1 \\leq n, m, K \\leq 5000)$，分别表示迷宫的尺寸和 Michael 指令的长度。\n\n接下来 $n$ 行，第 $i$ 行包含一个字符串 $A_i$，表示迷宫的第 $i$ 行。如果 $A_{(i, j)} =$\"#\"，则迷宫的 $(i, j)$ 位置是障碍物；否则，$A_{(i, j)} =$\".\"。\n\n最后一行包含一个字符串 $S$，即 Michael 的机器人接收到的指令。$S$ 中的每个字符都是 'R'、'D' 或 '?' 之一。\n\n输出机器人遵循指令而不撞到障碍物或离开迷宫的方案数，对 $10^9 + 7$ 取模的结果。\n\n在第一个例子中，机器人可能遵循的六种指令为：$D D R, D R D, R D D, R R D, R D R$ 和 $D R R$。\n\n在第二个例子中，机器人可能遵循的唯一指令是 $D D R D$。在这种情况下，机器人将遵循路径：\n\n$$(1,1)\\to(2,1)\\to(3,1)\\to(3,2)\\to(4,2)$$\n\n"},{"iden":"input","content":"第一行包含三个整数 $n, m, K$ $(1 \\leq n, m, K \\leq 5000)$，分别表示迷宫的尺寸和 Michael 指令的长度。接下来 $n$ 行，第 $i$ 行包含一个字符串 $A_i$，表示迷宫的第 $i$ 行。如果 $A_{(i, j)} =$\"#\"，则迷宫的 $(i, j)$ 位置是障碍物；否则，$A_{(i, j)} =$\".\"。最后一行包含一个字符串 $S$，即 Michael 的机器人接收到的指令。$S$ 中的每个字符都是 'R'、'D' 或 '?' 之一。"},{"iden":"output","content":"机器人遵循指令而不撞到障碍物或离开迷宫的方案数，对 $10^9 + 7$ 取模的结果。"},{"iden":"examples","content":"输入\n3 3 3\n...\n...\n...\n???\n输出\n6\n\n输入\n4 4 4\n.##.\n.#..\n....\n....\nD??D\n输出\n1\n\n输入\n9 7 10\n.......\n..##...\n......#\n..##..#\n.......\n.#.....\n.....#.\n...#...\n.....##\n?D?DD?R?DD\n输出\n3\n"},{"iden":"note","content":"在第一个例子中，机器人可能遵循的六种指令为：$D D R, D R D, R D D, R R D, R D R$ 和 $D R R$。在第二个例子中，机器人可能遵循的唯一指令是 $D D R D$。在这种情况下，机器人将遵循路径：$$(1,1)\\to(2,1)\\to(3,1)\\to(3,2)\\to(4,2)$$"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, K \\in \\mathbb{Z}^+ $ denote the dimensions of the maze and the length of the command string.  \nLet $ M \\in \\{ \\text{`.`}, \\text{`#`} \\}^{n \\times m} $ be the maze grid, where $ M[i][j] = \\text{`#`} $ denotes an obstacle at position $ (i, j) $, and $ M[i][j] = \\text{`.`} $ denotes a free cell.  \nLet $ S \\in \\{ \\text{`R`}, \\text{`D`}, \\text{`?`} \\}^K $ be the received command string.  \n\nLet $ \\mathcal{P} \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the set of valid positions (i.e., $ M[i][j] = \\text{`.`} $).  \nLet $ \\text{start} = (1, 1) $.  \n\nLet $ \\text{move}(c, (x, y)) $ denote the next position after applying command $ c \\in \\{ \\text{`R`}, \\text{`D`} \\} $ from $ (x, y) $:  \n- $ \\text{move}(\\text{`R`}, (x, y)) = (x, y+1) $  \n- $ \\text{move}(\\text{`D`}, (x, y)) = (x+1, y) $  \n\n**Constraints**  \n1. $ 1 \\leq n, m, K \\leq 5000 $  \n2. $ M[1][1] = \\text{`.`} $  \n3. For all $ (i, j) $, if $ M[i][j] = \\text{`#`} $, then $ (i, j) \\notin \\mathcal{P} $.  \n4. The robot must remain within bounds: $ 1 \\leq x \\leq n $, $ 1 \\leq y \\leq m $ at all steps.  \n\n**Objective**  \nCompute the number of valid command sequences $ S' \\in \\{ \\text{`R`}, \\text{`D`} \\}^K $ such that:  \n- $ S'[i] = S[i] $ if $ S[i] \\neq \\text{`?`} $,  \n- $ S'[i] \\in \\{ \\text{`R`}, \\text{`D`} \\} $ if $ S[i] = \\text{`?`} $,  \n- The robot’s path $ p_0 = (1,1), p_1, \\dots, p_K $, where $ p_i = \\text{move}(S'[i], p_{i-1}) $, satisfies $ p_i \\in \\mathcal{P} $ for all $ i \\in \\{1, \\dots, K\\} $.  \n\nOutput the count modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}