{"problem":{"name":"[ICPC 2020 Shanghai R] Sum of Log","description":{"content":"Given two non-negative integers $X$ and $Y$, determine the value of  $$ \\sum_{i=0}^{X}\\sum_{j=[i=0]}^{Y}[i\\&j=0]\\lfloor\\log_2(i+j)+1\\rfloor $$ modulo $10^9+7$ where - $\\&$ denotes bitwise AND; - $[A]$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9821"},"statements":[{"statement_type":"Markdown","content":"Given two non-negative integers $X$ and $Y$, determine the value of \n$$ \\sum_{i=0}^{X}\\sum_{j=[i=0]}^{Y}[i\\&j=0]\\lfloor\\log_2(i+j)+1\\rfloor $$\nmodulo $10^9+7$ where\n- $\\&$ denotes bitwise AND;\n- $[A]$ equals 1 if $A$ is true, otherwise $0$;\n- $\\lfloor x\\rfloor$ equals the maximum integer whose value is no more than $x$.\n\n## Input\n\nThe first line contains one integer $T\\,(1\\le T \\le 10^5)$ denoting the number of test cases.\n\nEach of the following $T$ lines contains two integers $X, Y\\,(0\\le X,Y \\le 10^9)$ indicating a test case.\n\n## Output\n\nFor each test case, print one line containing one integer, the answer to the test case.\n\n[samples]\n\n## Note\n\nFor the first test case:\n- Two $(i,j)$ pairs increase the sum by 1: $(0, 1), (1, 0)$\n- Six $(i,j)$ pairs increase the sum by 2: $(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0)$\n\nSo the answer is $1\\times 2 + 2\\times 6 = 14$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9821","tags":["2020","上海","O2优化","数位 DP","ICPC"],"sample_group":[["3\n3 3\n19 26\n8 17","14\n814\n278"]],"created_at":"2026-03-03 11:09:25"}}