新冠疫情爆发后，明明每天都会去关注新增的病例数，看着这些数据，就进入了梦境。
在梦里面，他遇到了一串特殊的序列：1, 1, 1, 3, 5, 9, 17, …这些数字从第4项开始，每项都是前 3 项的和。
在梦境中，他找到了一扇传送门，想要离开梦境，并需输入开门的密码。
根据提示，开门的密码就是这组序列的第n项的最后四位，如果不满4位，需要用0补全
现在，请你帮他算出密码，助他离开梦境。

输入一行一个整数n（0<n<=1000000)。

输出一行一个整数，即开门密码。如果第n项密码不满4位，则需要用0补全。

提示第二个样例：
输入 1000
输出 4431

样例数据范围：
30%的数据，n<=10
100%的数据，n<=1000000