Background

2019年蓝桥杯省赛 C++ B组 填空题

Description

给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求 第20190324 项的最后4 位数字。

Format

Input

无

Output

输出答案即可

Samples

无

无

Limitation

1s, 1024KiB for each test case.