{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"这一周轮到兔子的小组出题了，由于不知道应该出什么题好的兔子在实验室群中询问大家喜爱的题目，大家都积极回答，在总结了大家的回复后，兔子发现大家都很喜欢做数学题，于是兔子打算出一个数学题来为难大家：\u003cp\u003e\n \n\n\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e在斐波那契整数序列中，对于n≥2， \u003ci\u003eF\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e \u003d 0, \u003ci\u003eF\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003d 1, and \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e \u003d \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e − 1\u003c/sub\u003e + \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e − 2\u003c/sub\u003e。例如，斐波那契序列的前十项是：\u003c/p\u003e\u003cp align\u003d\"center\"\u003e0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …\u003c/p\u003e\u003cp\u003e斐波那契数列的另一个公式是\n\n\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/23da167d8116d97497f11a1e8ecd74fa?v\u003d1583812571\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003cp\u003e给定整数\u003ci\u003en\u003c/i\u003e，你的目标是计算 \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e\u003c/p\u003e\u003c/span\u003e\n \u003c/div\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e输入的测试文件将包含多个测试用例。每个测试用例由包含一个 n (0 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1,000,000,000). 文件结尾用包含数字-1的单行表示。\u003c/p\u003e\u003c/span\u003e\n \u003c/div\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e对于每个测试样例,输出Fn ，如果这个数是0，就输出0 ( 打印\u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e mod 10000).\u003c/p\u003e\u003c/span\u003e\n \u003c/div\u003e\n"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e0\n9\n999999999\n1000000000\n-1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e0\n34\n626\n6875\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e提醒一下，矩阵乘法是关联的，两个2×2矩阵的乘积由下式给出：\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/984c6270154c8fdd9f92e6bcdccc108b?v\u003d1583812571\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003cp\u003e此外，请注意，将任何2×2矩阵提高到0的幂即为单位矩阵：\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/9edfa7d7905bf6c423a7108ebfb9adf6?v\u003d1583812571\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003c/span\u003e\n \u003c/div\u003e"}}]}