暂无测试数据。

题目描述

两个国家 A 国和 B 国，货币单位分别为 \(\alpha\) 和 \(\beta\)，它们的汇率为：

• \(90\alpha\to 100\beta\)
• \(90\beta\to 100\alpha\)

一个人拥有 \(100\alpha\) 和 \(100\beta\)，且第 \(i\) 次后，他会额外获得 \(2^i\times 100\) 当前拥有的最少的货币。

他在两国间进行交易，交易方式如下：

• 第一次，用 \(100\alpha\) 购买 \(10\alpha\) 的货物，剩下 \(90\alpha\)，兑换成 \(100\beta\)，这时他有 \(200\beta\)。
• 第二次，用 \(200\beta\) 购买 \(20\beta\) 的货物，剩下 \(180\beta\)，兑换成 \(200\alpha\)，加上上次获得的 \(200\alpha\)，这时他有 \(400\alpha\)。
• 第三次，……

求第 \(n\) 次时他拥有价值多少的 货物（这时 \(1\alpha=1\beta\)）。

输入格式

一个数 \(n\)。

输出格式

仅一行，即第 \(n\) 次时他拥有价值多少的货物。

输入输出样例

输入样例 #1

2

输出样例 #1

30

说明/提示

样例 1 说明

此时他拥有一个 \(10\alpha\) 的货物和一个 \(20\beta\) 的货物，总价值为 \(30\)。

注意事项

令答案为 \(ans\)，你只需要输出 \(\dfrac{ans}{10}\bmod (10^7+7)\times 10\) 的值。

数据规模与约定

对于 \(100\%\) 的数据，都有 \(1\le n\le 10^9\)。

来源

SR 团选拔赛 Round 1 T2

idea: CSP_Sept