题目描述

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

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

输入格式

一行一个正整数 $n$ 。

输出格式

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

样例

样例输入1

1

样例输出1

1

样例输入2

3

样例输出2

7

数据范围与提示

$1 \le n \le 10^7$