{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cb\u003eKazaQ\u003c/b\u003e has a knapsack with volume $2 \\cdot n$ and $n$ kinds of food, where the $i$-th food\u0027s volume is $i$ and the number of it is $a_i$ $(1 \\leq i \\leq n)$ meaning that the number of the $i$-th food that \u003cb\u003eKazaQ\u003c/b\u003e would like to store into the knapsack is no more than $a_i$, otherwise he would feel sick. \u003cb\u003eKazaQ\u003c/b\u003e has a unique taste, therefore all the $a_i$ are distinct.\u003cbr\u003e\u003cbr\u003e\u003cb\u003eKazaQ\u003c/b\u003e plans to make a journey but after that he needs to store some food and one piece of equipment into the knapsack. He has $m$ pieces of equipment, of which the $i$-th piece\u0027s volume is $b_i$ $(1 \\leq i \\leq n)$. Notice that volumes of different pieces may be the same.\u003cbr\u003e\u003cbr\u003eAssuming that two plans are distinct if and only if they contain different pieces of equipment or there exists at least one integer $k$ $(1 \\leq k \\leq n)$ satisfying the number of the $k$-th food to store into the knapsack in this two plans are different, \u003cb\u003eKazaQ\u003c/b\u003e is intend to know what is the total number of distinct plans for storing one piece of equipment and some food into the knapsack fully. Can you help him?\u003cbr\u003e\u003cbr\u003eThe answer may be very large, so you only need to give the value of the answer modulo $10^9 + 7$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains multiple test cases.\u003cbr\u003e\u003cbr\u003eFor each test case:\u003cbr\u003e\u003cbr\u003eThe first line contains two positive integers $n$ and $m$, satisfying $1 \\leq n \\leq 5 \\cdot 10^4, 1 \\leq m \\leq 2 \\cdot n$.\u003cbr\u003e\u003cbr\u003eThe second line contains $n$ distinct non-negative integers $a_1, a_2, \\cdots, a_n$, satisfying $0 \\leq a_1 \u0026lt; a_2 \u0026lt; \\cdots \u0026lt; a_n \\leq 2 \\cdot n$.\u003cbr\u003e\u003cbr\u003eThe third line contains $m$ positive integers $b_1, b_2, \\cdots, b_m$, satisfying $1 \\leq b_1, b_2, \\cdots, b_m \\leq 2 \\cdot n$.\u003cbr\u003e\u003cbr\u003eAbout $100$ test cases in total, where no more than $5$ cases satisfy $n \\geq 10^3$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output \"\u003cb\u003eCase #$x$: $y$\u003c/b\u003e\" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\r\n1\r\n1\r\n2 2\r\n1 2\r\n3 4\r\n3 3\r\n1 2 3\r\n2 3 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\nCase #2: 2\r\nCase #3: 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}