E1. Rubik‘s Cube Coloring (easy version) 貪心，滿二叉樹（1300）

題意 ：

• 給定一個層數為k的滿二叉樹，結點編号為标準的層序周遊的編号
• 魔方有六個面，如圖，每個面一個顔色
• 樹上的結點的顔色也是這六個顔色之一，但是兩個相鄰結點的顔色必須是 魔方中，顔色相鄰的兩種顔色
• 求這個滿二叉樹的合法染色方案 取模1e9 + 7

思路 ：

• 假設固定根，每個結點必須和其父節點顔色滿足要求
• 不管父節點顔色如何，這個結點都隻有4種顔色可選
• 答案就是 6 ∗ 4 結 點 個 數 − 1 6 * 4^{結點個數-1} 6∗4結點個數−1
• 結點個數等于 2 k − 1 2^k-1 2k−1
• 這裡 2 k 2^k 2k不會爆ll，可以直接去算

#include <iostream>
#include <cstring>
#include <algorithm>
#define endl '\n'

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll qmi(ll a, ll b)
{
    ll res = 1 % mod;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve()
{
    ll k;
    cin >> k;
//    cout << 6ll * qmi(4ll, qmi(2ll, k) - 2ll) % mod << endl;
    
//    ll tmp = ((qmi(2ll, k) % mod - 2ll) % mod + mod) % mod;
//    cout << 6ll * qmi(4ll, tmp) % mod << endl;
    
    cout << 6ll * qmi(4ll, (1ll << k) - 2ll) % mod << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int _ = 1;
//    cin >> _;
    
    while (_ -- )
    {
        solve();
    }
}