题目描述

Actci偶然发现了一个矿洞，这个矿洞的结构类似与一棵二叉树，Actci发现的矿洞恰好位于根节点处，为了尽快挖掘，Actci找来了她的小伙伴们来帮忙，由于地质原因，每天小伙伴们只能打通到一条到子节点的道路(不消耗时间)，也就是说每天一个节点只能向一个子节点建设道路，走一条路需要一天的时间，当发现一条道路后，会有一部分小伙伴选择留下来继续勘测，假设小伙伴们有无数个，树的深度足够大，问第n天最多共建设几条道路。

输入格式

一行，一个数n。

输出格式

一行，一个数表示最多建设的道路数，答案对$10000000007$取模。

样例

2

3

100

6531708670

提示

对于10%的数据$n \\le 10$

对于40%的数据$n \\le 1000$

对于70%的数据$n\\le1e6$

对于100%的数据$n \\le 5e6$

来自机械20-2 任满意