Problem1715--快速幂-2的n次方

1715: 快速幂-2的n次方

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 239  Solved: 117
[Status] [Submit] [Creator:]

Description

我们乘 2n 为 “2 的 n 次方”,它表示 n 个 2 相乘的乘积。如: 22 = 2 × 2 = 4,25 = 2 × 2 × 2 × 2 × 2 = 32。

现在给你一个整数 n,求 2n 除以 1000 的余数。

Input

一个整数 n(1 ≤ n ≤ 2,000,000,000)。

Output

输出一个整数,表示 2n 除以 1000 的余数。

Sample Input Copy

【样例输入1】
5
【样例输出1】
32
【样例输入2】
20
【样例输出2】
576

Source/Category

 提高A