给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。
求第 n (n <= 20190324 ) 项的最后 4 位数字。
一行整数 n。
按题目要求输出。
样例输入
7
样例输出
17