#P2716. nEo的玄学商店

nEo的玄学商店

玄学商人 nEo  的玄学商店非常玄学,这家商店出售的苏打水是一块钱一瓶,但是如果你想买第二瓶,玄学商人 nEo 就会把它的价格提高到两块钱,第三瓶的价格是四块钱。也就是说,你买第 i 瓶苏打水的价格是 2^(i - 1) 元。

今天 mjz 想喝苏打水了,但他非常吝啬,于是他把你抓去买苏打水。 告诉你他想喝 n 瓶苏打水,请计算你需要花多少钱才能买下这些苏打水。由于答案可能很大你只需要输出答案对 1e9 取模的结果即可。

Input

一行一个正整数  n。

Output

一行一个正整数表示答案取模后的结果。

Sample Input

1

Sample Output

1

HINT


1 ≤ n ≤ 1e7

Source