{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRenan was driving the Cirque Du Soleil artists in his blue towner. Unfortunately the towner rolled over in Paralela (a well known avenue in Soteropolis). The $$$N$$$ circus performers have each a distinct value between $$$1$$$ and $$$N$$$. During the rollover the performers left the towner through the window, while doing some acrobatics and leaving poor Renan by himself inside the vehicle. \u003c/p\u003e\u003cp\u003eEveryone knows that Paralela is the habitat of an infamous Jaguar. This Jaguar wants to ambush the performers and get some food. Let $$$S$$$ be the value of satisfaction of its lunch. $$$S$$$ follows a totally arbitrary formula that can be calculated as shown below: \u003c/p\u003e\u003ccenter\u003e $$$S$$$ \u003d $$$\\sum\\limits_{T \\subseteq P, T \\neq \\emptyset}|\\max(T) - \\min(T)|$$$, \u003c/center\u003e\u003cp\u003ewhere $$$P$$$ is the set of performers $$$\\{1, 2, \\dots, N\\}$$$, $$$\\max(T)$$$ is the maximum value in $$$T$$$ and $$$\\min(T)$$$ is the minimum value in $$$T$$$.\u003c/p\u003e\u003cp\u003eRenan feels like he could be in trouble, so he wants to know the satisfaction the Jaguar will get by ambushing the performers. Since Renan is not good at maths, you need to calculate $$$S$$$ for him. Note that this value can be big, so you only need to output it $$$S$$$ module $$$10^9 + 7$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer $$$T$$$ ($$$1 \\leq T \\leq 10^{4}$$$), the number of testcases to be processed.\u003c/p\u003e\u003cp\u003eEach of the following $$$T$$$ lines contains an integer $$$N$$$ ($$$1 \\leq N \\leq 10^{18}$$$) – the number of performers Renan was driving with him.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput $$$T$$$ lines, one for each testcase. In every line you need to print the value of $$$S$$$ module $$$10^9 + 7$$$ for such testcase.\u003c/p\u003e"}},{"title":"Examples","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\u003e4\n2\n3\n7\n5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n6\n522\n72\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}