{"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":"\n\u003cp\u003eTrong toán học, các số Fibonacci hoặc dãy Fibonacci là các số trong dãy số nguyên sau:\u003c/p\u003e\n\u003cp align\u003d\"center\"\u003e1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...\u003c/p\u003e\n\u003cp\u003eTheo định nghĩa, hai số đầu tiên trong dãy Fibonacci là 1 và 1, và mỗi số tiếp theo là tổng của hai số trước đó. Trong thuật ngữ toán học, dãy \u003cvar\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e số Fibonacci được định nghĩa bởi mối quan hệ tái phát \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 với giá trị khởi đầu \u003cvar\u003eF\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e \u003d 1 và \u003cvar\u003eF\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e \u003d 1.\u003c/p\u003e\n\u003cp\u003eVà nhiệm vụ của bạn là tìm Σ\u003cvar\u003eF\u003csub\u003ei\u003c/sub\u003e\u003csup\u003eK\u003c/sup\u003e\u003c/var\u003e, tổng của lũy thừa \u003cvar\u003eK\u003c/var\u003e-th của \u003cvar\u003eN\u003c/var\u003e số đầu tiên trong dãy Fibonacci. Vì kết quả có thể rất lớn, bạn nên đưa ra phần dư của kết quả chia cho 1000000009.\u003c/p\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eCó nhiều test case. Dòng đầu tiên của input là một số nguyên \u003cvar\u003eT\u003c/var\u003e cho biết số lượng test case. Đối với mỗi test case:\u003c/p\u003e\n\u003cp\u003eCó hai số nguyên \u003cvar\u003eN\u003c/var\u003e và \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).\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eĐối với mỗi test case, đưa ra phần dư của kết quả chia cho 1000000009.\u003c/p\u003e\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\n \u003cpre\u003e5\n10 1\n4 20\n20 2\n9999 99\n987654321987654321 98765\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\n \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\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eTest case đầu tiên, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 \u003d 143.\u003c/p\u003e\n\u003cp\u003eTest case thứ hai, 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, và 3487832979 \u003d 3 * 1000000009 + 487832952, vì vậy output là 487832952.\u003c/p\u003e"}}]}