{"problem":{"name":"C1. Dawn of the planet of the Rastas","description":{"content":"Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.  Rastas' army has 2n - 1 soldiers and the strength of soldier numbe","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":15000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070C1"},"statements":[{"statement_type":"Markdown","content":"Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital. \n\nRastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1).\n\nIf the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to:\n\nAs the minister of Mike, it's your duty to calculate S modulo 109 + 7.\n\nSubtasks:\n\nEach subtask consists of one testcase.\n\nInput consists of one integer, n.\n\nPrint the answer modulo 109 + 7 in a single line.\n\n## Input\n\nEach subtask consists of one testcase.Input consists of one integer, n.\n\n## Output\n\nPrint the answer modulo 109 + 7 in a single line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ m = 2^n - 1 $.  \nFor $ i \\in \\{1, 2, \\dots, m\\} $, define $ s(i) = \\text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 10^6 $ (implied by subtask context and modulus $ 10^9 + 7 $)  \n\n**Objective**  \nCompute:  \n$$\nS = \\sum_{i=1}^{2^n - 1} \\sum_{j=1}^{2^n - 1} \\gcd(s(i), s(j)) \\cdot [\\gcd(i, j) = \\gcd(s(i), s(j))]\n$$  \nmodulo $ 10^9 + 7 $.  \n\n(Note: The condition “If $ \\gcd(a, b) = \\gcd(\\text{popcount}(a), \\text{popcount}(b)) $” implies that the sum is over pairs $ (i,j) $ where $ \\gcd(i,j) = \\gcd(s(i), s(j)) $, and for such pairs, the contribution is $ \\gcd(s(i), s(j)) $. All other pairs contribute 0.)","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070C1","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}