Problem3441--周周练-第3周：递推-国王的金币

3441: 周周练-第3周：递推-国王的金币

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 36  Solved: 30
[Status] [Submit] [Creator:]

Description

已知小明每天都会从国王哪里领到金币。

小明第一天领到了 2 枚金币。

从第二天开始，小明每一天领到的金币都是前一天领到的金币的两倍 + 2 枚。

但是由于当地的税收政策，当小明一天领到的金币数达到一千枚时，整千的部分都得交税，这也就是说小明实际领到的金币数量是他原本应该拿到的金币数量除以 1000 的余数。

问：第 n 天小明领到了多少枚金币？

Input

一个整数 n（1 ≤ n ≤ 1000）。

Output

输出一个整数，表示小明第 n 天领到的金币数。

Sample Input Copy 

20

Sample Output Copy 

150

HINT

【样例解释】
· 小明第 1 天领到的金币数量是 (0 × 2 + 2) % 1000 = 2 枚
· 小明第 2 天领到的金币数量是 (2 × 2 + 2) % 1000 = 6 枚
· 小明第 3 天领到的金币数量是 (6 × 2 + 2) % 1000 = 14 枚
· 小明第 4 天领到的金币数量是 (14 × 2 + 2) % 1000 = 30 枚
· 小明第 5 天领到的金币数量是 (30 × 2 + 2) % 1000 = 62 枚
· 小明第 6 天领到的金币数量是 (62 × 2 + 2) % 1000 = 126 枚
· 小明第 7 天领到的金币数量是 (126 × 2 + 2) % 1000 = 254 枚
· 小明第 8 天领到的金币数量是 (254 × 2 + 2) % 1000 = 510 枚
· 小明第 9 天领到的金币数量是 (510 × 2 + 2) % 1000 = 22 枚
· 小明第 10 天领到的金币数量是 (22 × 2 + 2) % 1000 = 46 枚
· 小明第 11 天领到的金币数量是 (46 × 2 + 2) % 1000 = 94 枚
· 小明第 12 天领到的金币数量是 (94 × 2 + 2) % 1000 = 190 枚
· 小明第 13 天领到的金币数量是 (190 × 2 + 2) % 1000 = 382 枚
· 小明第 14 天领到的金币数量是 (382 × 2 + 2) % 1000 = 766 枚
· 小明第 15 天领到的金币数量是 (766 × 2 + 2) % 1000 = 534 枚
· 小明第 16 天领到的金币数量是 (534 × 2 + 2) % 1000 = 70 枚
· 小明第 17 天领到的金币数量是 (70 × 2 + 2) % 1000 = 142 枚
· 小明第 18 天领到的金币数量是 (142 × 2 + 2) % 1000 = 286 枚
· 小明第 19 天领到的金币数量是 (286 × 2 + 2) % 1000 = 574 枚
· 小明第 20 天领到的金币数量是 (574 × 2 + 2) % 1000 = 150 枚

Source/Category

周周练-提高A 
[Submit] [Status]