题目描述

强哥在 $IKUN宝宝幼儿园$学会了二进制，强哥觉得二进制很神奇，任何一个整数都可以由一些互不相同的 $2$ 的次幂表示，例如 $7$ 的二进制是 $111_{2}$，所以 $7 = 4 + 2 + 1$。

幼儿园的大雄老师给大家布置了一项作业，如果把互不相同这一条件去掉，会有多少种方案呢，由于方案数过大，需要答案对 $10^9 + 7$取模？

强哥毕竟刚上幼儿园，啥都不懂，于是他只好向你寻求帮助。

输入格式

一行一个正整数 $n$ $(1 \le n \le 10^6)$

输出格式

一行一个数表示答案对 $10^9 + 7$取模的结果

7

6

8

10

9

10

提示

对于样例1：$7 = 4 + 2 + 1 = 4 + 1 + 1 + 1 = 2 + 2 + 2 + 1 = 2 + 2 + 1 + 1 + 1 = 2 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1$