你有一个大小为n×n的矩阵, 你可以在矩阵中自由地填写数字
假如将这个矩阵每个位置都填上0或1这两种数字, 不难计算: 共有2的(n×n)次方这么多种填写方案
但是小度不喜欢偶数, 它希望矩阵的任意某行或任意某列的数字之和均为奇数
那么按上述规则将n×n矩阵用0或1填满, 将有多少种方案去填写呢? 你能帮小度计算出来吗?
答案可能很大, 请输出答案对1000000007 (10⁹+7)取模后的结果
格式
输入格式
输入仅包含一个正整数n (1≤n≤109), 含义如题面所述
输出格式
输出一个非负整数, 含义如题面所述
