题目描述

传说中，只有能够将力量完美分解的勇者，才能获得王国中最强大的能量— —异或之力。 对于每一个 01 字符串都含有一定异或之力。假设某个 01 字符串所代表的 十进制数为 C，当 C 小于等于 1 时异或之力为 0；当 C 大于 1 时，将 C 分 解成任意两个正整数 A 和 B（A > 0，B > 0，A + B = C）, 得到 A 异或 B 的最 大值为 P , 异或最小值为 Q , 异或之力即为 P 和 Q 的差值。 作为王国的继承者，你被赋予了一个正整数 n 。你的任务是寻找所有长度为 n 的 01 字符串（注意：字符串可含前导零，即 (0011) 2 是合法的，与 (11) 2 相 同都代表着数字 3）中，最大异或之力是多少。这个数可能很大，请输出其与 10 9 +7 取模之后的结果。 异或运算（⊕）：对于两个二进制数的每一位，如果相同则为 0，不同则为 1。例如，6 (110) ⊕ 3 (011) = 5 (101) , 9 (1001) ⊕ 3 (0011) = 10 (1010)。

输入格式

一行包含一个正整数 n ，表示字符串的长度。

输出格式

一个整数，表示最大异或之力。

输入输出样例 #1

输入 #1

3

输出 #1

6