{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eStill not knowing the name of the girl from the previous problem, Sasha decided to make inquiries, he was lucky that he had a database of university and VK at hand. It was found that Ira is an excellent student for four years and wanted to get a bachelor\u0027s degree, and as it turned out, a master\u0027s degree and PhD. And you never know what else?..\u003c/p\u003e\n\n\u003cp\u003e--- \u003cem\u003eHow much will it be in the sum\u003c/em\u003e? --- Sasha thought with delight (note: in Russian for \"power\" and \"degree\" is used the same word), while subconsciously recalling a recent problem from the contest which he has not solved. Two numbers are given \u003cstrong\u003eN\u003c/strong\u003e and \u003cstrong\u003eK\u003c/strong\u003e, compute\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/bb/bb6cfd02c724d122569ca196cc4dba49c5942363.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eThe \u001cfirst line contains \u003cstrong\u003eQ\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eQ\u003c/strong\u003e ≤ \u003cstrong\u003e41000\u003c/strong\u003e) --- the number of queries. Each of the following \u003cstrong\u003eQ\u003c/strong\u003e lines contains two numbers \u003cstrong\u003eN\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e ≤ \u003cstrong\u003e10^9\u003c/strong\u003e) and \u003cstrong\u003eK \u003c/strong\u003e(\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eK\u003c/strong\u003e ≤ \u003cstrong\u003e1000\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each query on a separate line write one number --- the sum of \u003cstrong\u003eK\u003c/strong\u003e-th powers of positive integers from \u003cstrong\u003e1\u003c/strong\u003e to \u003cstrong\u003eN\u003c/strong\u003e modulo \u003cstrong\u003e1000000007\u003c/strong\u003e .\u003c/p\u003e\n\n"}},{"title":"Example","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 1\n4 2\n3 3\n11 11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n30\n36\n675987247\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}