{"problem":{"name":"J. Journey with Knapsack","description":{"content":"_KazaQ_ has a knapsack of volume $2 n$ and $n$ kinds of food, where the volume of one piece of the $i$-th kind of food is $i$, and the number of pieces of that kind he would like to put into the knaps","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225J"},"statements":[{"statement_type":"Markdown","content":"_KazaQ_ has a knapsack of volume $2 n$ and $n$ kinds of food, where the volume of one piece of the $i$-th kind of food is $i$, and the number of pieces of that kind he would like to put into the knapsack is no more than $a_i$. If he put too much food in it, he would feel uncomfortable. Besides, since he has an odd taste for food, $a_1$, $a_2$, $\\\\dots$, $a_n$ are distinct.\n\n_KazaQ_ plans to go on a journey. Before that, he needs to take some food and one type of equipment he owns. He has $m$ types of equipment, where the $i$-th one's volume is $b_i$, and some types of equipment may have the same volume.\n\n_KazaQ_ intends to know in how many ways he can pack up his belongings into his knapsack to make it full, where two ways are considered different if and only if the types of equipment he carries vary, or in case they are the same, the numbers of at least one kind of food in these two ways are different. Can you help him?\n\nThe answer may be extremely large, so you should output the answer modulo $(10^9 + 7)$ instead.\n\nThe input contains multiple (about $100$) test cases.\n\nFor each test case, the first line contains two integers $n$, $m$ ($1 <= n <= 5 times 10^4$, $1 <= m <= 2 n$).\n\nThe second line contains $n$ distinct integers $a_1$, $a_2$, $\\\\dots$, $a_n$ ($0 <= a_1 < a_2 < \\\\dots < a_n <= 2 n$).\n\nThe third line contains $m$ integers $b_1$, $b_2$, $\\\\dots$, $b_m$ ($1 <= b_1, b_2, \\\\dots, b_m <= 2 n$).\n\nIt is guaranteed that no more than $5$ test cases satisfy that $n >= 10^3$.\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\n## Input\n\nThe input contains multiple (about $100$) test cases.For each test case, the first line contains two integers $n$, $m$ ($1 <= n <= 5 times 10^4$, $1 <= m <= 2 n$).The second line contains $n$ distinct integers $a_1$, $a_2$, $\\\\dots$, $a_n$ ($0 <= a_1 < a_2 < \\\\dots < a_n <= 2 n$).The third line contains $m$ integers $b_1$, $b_2$, $\\\\dots$, $b_m$ ($1 <= b_1, b_2, \\\\dots, b_m <= 2 n$).It is guaranteed that no more than $5$ test cases satisfy that $n >= 10^3$.\n\n## Output\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a strictly increasing sequence of integers with $ 0 < a_1 < a_2 < \\dots < a_n \\leq 2n $.  \nLet $ B = (b_1, b_2, \\dots, b_m) $ be a sequence of integers with $ 1 \\leq b_i \\leq 2n $, representing equipment volumes (with possible duplicates).  \nLet the knapsack capacity be $ C = 2n $.  \n\nLet $ \\mathcal{F} $ be the set of food configurations:  \n$ \\mathcal{F} = \\left\\{ (x_1, x_2, \\dots, x_n) \\in \\mathbb{Z}_{\\geq 0}^n \\mid \\sum_{i=1}^n i \\cdot x_i \\leq 2n \\text{ and } 0 \\leq x_i \\leq a_i \\text{ for all } i \\right\\} $.  \n\nLet $ \\mathcal{E} = \\{ b_1, b_2, \\dots, b_m \\} $ be the multiset of equipment volumes.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5 \\times 10^4 $, $ 1 \\leq m \\leq 2n $  \n2. $ a_i \\in \\mathbb{Z} $, strictly increasing, $ 0 < a_1 < \\dots < a_n \\leq 2n $  \n3. $ b_i \\in \\mathbb{Z} $, $ 1 \\leq b_i \\leq 2n $  \n4. At most 5 test cases have $ n \\geq 10^3 $  \n\n**Objective**  \nCompute the number of valid packings such that the total volume is exactly $ 2n $, where each packing consists of:  \n- Exactly one piece of equipment of volume $ b_j $ for some $ j \\in \\{1, \\dots, m\\} $,  \n- And a food configuration $ (x_1, \\dots, x_n) \\in \\mathcal{F} $ such that:  \n$$\n\\sum_{i=1}^n i \\cdot x_i + b_j = 2n\n$$  \n\nTwo packings are distinct if either:  \n- The equipment type differs, or  \n- The equipment type is the same but the food configuration differs.  \n\nThus, the answer is:  \n$$\n\\sum_{j=1}^m \\left| \\left\\{ (x_1, \\dots, x_n) \\in \\mathcal{F} \\mid \\sum_{i=1}^n i \\cdot x_i = 2n - b_j \\right\\} \\right|\n$$  \n\nOutput the result modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}