{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eIn the Fibonacci integer sequence, \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 for \u003ci\u003en\u003c/i\u003e ≥ 2. For example, the first ten terms of the Fibonacci sequence are:\u003c/p\u003e\u003cp align\u003d\"center\"\u003e0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …\u003c/p\u003e\u003cp\u003eAn alternative formula for the Fibonacci sequence is\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/23da167d8116d97497f11a1e8ecd74fa?v\u003d1723712658\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003cp\u003eGiven an integer \u003ci\u003en\u003c/i\u003e, your goal is to compute the last 4 digits of \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eFor each test case, print the last four digits of \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e. If the last four digits of \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e mod 10000).\u003c/p\u003e\u003c/span\u003e"}},{"title":"Sample","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\u003e0\r\n9\r\n999999999\r\n1000000000\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n34\r\n626\r\n6875\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\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\u003d1723712658\" 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\u003d1723712658\" align\u003d\"middle\"\u003e.\u003c/p\u003e\u003c/span\u003e"}}]}