{"raw_statement":[{"iden":"statement","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\n\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"},{"iden":"input","content":"Each subtask consists of one testcase.Input consists of one integer, n."},{"iden":"output","content":"Print the answer modulo 109 + 7 in a single line."},{"iden":"examples","content":""}],"translated_statement":[{"iden":"statement","content":"由于 Mike 的暴行，Rastas 攻击了他的国家（当然为了帮助他的人民），并正向首都推进。\n\nRastas 的军队有 #cf_span[2n - 1] 名士兵，编号为 #cf_span[i] 的士兵的战斗力等于数字 #cf_span[i] 的二进制表示中 1 的个数（士兵编号从 #cf_span[1] 到 #cf_span[2n - 1]）。\n\n如果数字 #cf_span[a] 和 #cf_span[b] 的最大公约数为 #cf_span[gcd(a, b)]，则我们知道这支军队的战斗力 #cf_span[S] 等于：\n\n\n\n作为 Mike 的大臣，你的职责是计算 #cf_span[S] 对 #cf_span[109 + 7] 取模的结果。\n\n子任务：\n\n每个子任务包含一个测试用例。\n\n输入包含一个整数 #cf_span[n]。\n\n请在一行中输出答案对 #cf_span[109 + 7] 取模的结果。"},{"iden":"input","content":"每个子任务包含一个测试用例。输入包含一个整数 #cf_span[n]。"},{"iden":"output","content":"请在一行中输出答案对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":""}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be a positive integer. Define the set of soldiers indexed from $ 1 $ to $ 2^n - 1 $. For each soldier $ i $, define its strength as $ s(i) = \\text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $.\n\nThe army strength $ S $ is defined as:\n\n$$\nS = \\sum_{a=1}^{2^n - 1} \\sum_{b=1}^{2^n - 1} \\gcd(s(a), s(b))\n$$\n\nCompute $ S \\mod (10^9 + 7) $.","simple_statement":null,"has_page_source":false}