{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"斐波那契序列F1\u003d0,F2\u003d1,F3\u003d1,F4\u003d2...\n求斐波那契序列第n项Fn，但是你只要输出最后四位（不足四位则输出整个数）"}},{"title":"Input","value":{"format":"MD","content":"一个正整数n,(0≤n≤1000000000)\n包含多组输入，直到输入n\u003d-1"}},{"title":"Output","value":{"format":"MD","content":"斐波那契第n项的最后四位"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e0\n9\n999999999\n1000000000\n-1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e0\n34\n626\n6875\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"MD","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eAs a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/984c6270154c8fdd9f92e6bcdccc108b?v\u003d1566023601\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003cp\u003eAlso, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/9edfa7d7905bf6c423a7108ebfb9adf6?v\u003d1566023601\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003c/span\u003e\n \u003c/div\u003e"}}]}