问题描述

给定数列1，1，1，3，5，9，17，…，从第4个数开始，每项都是前3项的和，求第n项的最后4位数字。
输入：一个整数n，表示第n项
输出：一个整数，第n项的最后4位

测试案例1：
输入：

20211128

输出：

4063

测试案例2：
输入：

120211128

输出：

6175