{"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":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ m = 2^n - 1 $.  \nFor each $ i \\in \\{1, 2, \\dots, m\\} $, define the strength of soldier $ i $ as $ s(i) = \\text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $.  \n\n**Given**  \nFor all $ a, b \\in \\{1, 2, \\dots, m\\} $, it holds that $ \\gcd(a, b) = \\gcd(s(a), s(b)) $.  \n\n**Objective**  \nCompute:  \n$$\nS = \\sum_{a=1}^{m} \\sum_{b=1}^{m} \\gcd(s(a), s(b)) \\mod (10^9 + 7)\n$$","simple_statement":"Given an integer n, consider soldiers numbered from 1 to 2^n - 1.  \nThe strength of soldier i is the number of 1s in the binary representation of i.  \nThe total army strength S is the sum of gcd(i, j) for all pairs (i, j) where gcd(i, j) equals the strength of soldier gcd(i, j).  \nCompute S modulo 10^9 + 7.","has_page_source":false}