{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nIn mathematics, Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers of the following integer sequence:\n\u003c/p\u003e\n\n\u003cp align\u003d\"center\"\u003e\n1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...\n\u003c/p\u003e\n\n\u003cp\u003e\nBy definition, the first two numbers in the Fibonacci sequence are 1 and 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence \u003cvar\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e of Fibonacci numbers is defined by the recurrence relation \u003cvar\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e \u003d \u003cvar\u003eF\u003csub\u003en - 1\u003c/sub\u003e\u003c/var\u003e + \u003cvar\u003eF\u003csub\u003en - 2\u003c/sub\u003e\u003c/var\u003e with seed values \u003cvar\u003eF\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e \u003d 1 and \u003cvar\u003eF\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e \u003d 1.\n\u003c/p\u003e\n\n\u003cp\u003e\nAnd your task is to find Σ\u003cvar\u003eF\u003csub\u003ei\u003c/sub\u003e\u003csup\u003eK\u003c/sup\u003e\u003c/var\u003e, the sum of the \u003cvar\u003eK\u003c/var\u003e-th power of the first \u003cvar\u003eN\u003c/var\u003e terms in the Fibonacci sequence. Because the answer can be very large, you should output the remainder of the answer divided by 1000000009.\n\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003e\nThere are multiple test cases. The first line of input is an integer \u003cvar\u003eT\u003c/var\u003e indicates the number of test cases. For each test case:\n\u003c/p\u003e\n\n\u003cp\u003e\nThere are two integers \u003cvar\u003eN\u003c/var\u003e and \u003cvar\u003eK\u003c/var\u003e (0 \u0026lt;\u003d \u003cvar\u003eN\u003c/var\u003e \u0026lt;\u003d 10\u003csup\u003e18\u003c/sup\u003e, 1 \u0026lt;\u003d \u003cvar\u003eK\u003c/var\u003e \u0026lt;\u003d 100000).\n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003e\nFor each test case, output the remainder of the answer divided by 1000000009.\n\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\n10 1\n4 20\n20 2\n9999 99\n987654321987654321 98765\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e143\n487832952\n74049690\n113297124\n108672406\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\n\u003cp\u003e\nThe first test case, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 \u003d 143.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe second test case, 1\u003csup\u003e20\u003c/sup\u003e + 1\u003csup\u003e20\u003c/sup\u003e + 2\u003csup\u003e20\u003c/sup\u003e + 3\u003csup\u003e20\u003c/sup\u003e \u003d3487832979, and 3487832979 \u003d 3 * 1000000009 + 487832952, so the output is 487832952.\n\u003c/p\u003e\n"}}]}