{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e在斐波那契整数序列中，\u003ci\u003eF\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e \u003d 0，\u003ci\u003eF\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003d 1，对于 \u003ci\u003en\u003c/i\u003e ≥ 2，有 \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斐波那契序列的另一个公式为\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/23da167d8116d97497f11a1e8ecd74fa?v\u003d1713024043\" align\u003d\"middle\"\u003e。\u003c/p\u003e\u003cp\u003e给定一个整数 \u003ci\u003en\u003c/i\u003e，你的目标是计算 \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e 的最后4位数字。\u003c/p\u003e\u003c/span\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\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"}},{"title":"输出","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e对于每个测试用例，打印出 \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e 的最后四位数字。如果 \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e 的最后四位数字全为零，则打印‘0’；否则，省略任何前导零（即打印 \u003ci\u003eF\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e mod 10000）。\u003c/p\u003e\u003c/span\u003e"}},{"title":"示例","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"}},{"title":"提示","value":{"format":"HTML","content":"\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\u003d1713024043\" 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\u003d1713024043\" align\u003d\"middle\"\u003e。\u003c/p\u003e\u003c/span\u003e"}}]}