{"raw_statement":[{"iden":"statement","content":"You have n rectangles, each of which is described by three integers i, j and k. This indicates that the lower-left corner of the rectangle will be located at the point (i, 0) and the upper-right corner of the rectangle will be located at the point (j, k).  For example, if you have a description of four rectangles like this:  0 2 3  0 3 1  1 2 2  2 4 4  The area occupied by these rectangles will be as follows:\n\nThe total area in this case will be 14.  You are given n and n triples (i, j, k), your task is to compute the total area occupied by the rectangles which are described by the n triples.\n\nThe first line will contain a single integer T indicates the number of test cases. Each test case will consist of n + 1 lines, the first one will contain the number of rectangles n and the following n lines will be the description of the rectangles. Each description will be a triple (i, j, k) as mentioned above. The Constraints:  10 <= T <= 20  1 <= n <= 100  0 <= i < 100  1 <= j < 100  i != j  1 <= k <= 100 \n\nFor each test case, print a single integer in a separated line indicates the total area occupied by the rectangles.\n\n"},{"iden":"input","content":"The first line will contain a single integer T indicates the number of test cases. Each test case will consist of n + 1 lines, the first one will contain the number of rectangles n and the following n lines will be the description of the rectangles. Each description will be a triple (i, j, k) as mentioned above. The Constraints:  10 <= T <= 20  1 <= n <= 100  0 <= i < 100  1 <= j < 100  i != j  1 <= k <= 100 "},{"iden":"output","content":"For each test case, print a single integer in a separated line indicates the total area occupied by the rectangles."},{"iden":"examples","content":"Input140 2 30 3 11 2 22 4 4Output14"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ denote the bit-length of binary strings.  \n- Let $ A, B \\in \\{0,1\\}^n $ be binary strings of length $ n $, representing integers in big-endian format.  \n- Let $ C \\in \\{0,1\\}^n $ be an unknown binary string such that $ A \\mid C = B $, where $ \\mid $ denotes bitwise OR.\n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unbounded} $ (implied by \"several test cases\")  \n2. $ 1 \\le n \\le 100 $  \n3. $ A, B \\in \\{0,1\\}^n $ — strings of exactly $ n $ bits (no leading zeros assumed; padded to length $ n $)  \n\n**Objective**  \nFor each test case, compute the number of binary strings $ C \\in \\{0,1\\}^n $ satisfying:  \n$$\n\\forall i \\in \\{1, \\dots, n\\}, \\quad A_i \\mid C_i = B_i\n$$  \nIf no such $ C $ exists, output `\"IMPOSSIBLE\"`.  \nOtherwise, output the count modulo $ 1000000007 $.\n\n**Bitwise OR Constraint Analysis**  \nFor each bit position $ i $:  \n- If $ A_i = 1 $ and $ B_i = 0 $: **IMPOSSIBLE** (since $ 1 \\mid C_i \\geq 1 $)  \n- If $ A_i = 0 $ and $ B_i = 0 $: $ C_i = 0 $ → 1 choice  \n- If $ A_i = 0 $ and $ B_i = 1 $: $ C_i = 1 $ → 1 choice  \n- If $ A_i = 1 $ and $ B_i = 1 $: $ C_i \\in \\{0,1\\} $ → 2 choices  \n\nThus, total number of valid $ C $ is:  \n$$\n\\prod_{i=1}^{n} \n\\begin{cases}\n0 & \\text{if } A_i = 1 \\text{ and } B_i = 0 \\\\\n1 & \\text{if } A_i = 0 \\text{ and } B_i = 0 \\\\\n1 & \\text{if } A_i = 0 \\text{ and } B_i = 1 \\\\\n2 & \\text{if } A_i = 1 \\text{ and } B_i = 1 \\\\\n\\end{cases}\n$$","simple_statement":"Given two binary strings A and B of length n, find how many binary strings C exist such that A | C = B. If no such C exists, print \"IMPOSSIBLE\". Otherwise, print the count modulo 1000000007.","has_page_source":false}