Language: C++

#include <algorithm>
#include <array>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <istream>

#include <map>
#include <math.h>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace asl
{
    
    void asl_assert(bool condition)
    {

    }
 
#include <stdint.h>

    template <typename T>
    using vec = std::vector<T>;

    template <typename T>
    std::istream &operator>>(std::istream &is, std::vector<T> &vec)
    {
        for (auto &value : vec)
            is >> value;
        return is;
    }

} 

#include <experimental/optional>

namespace asl
{
    
    const int m1000000007 = 1000000007;
    
    int MOD = m1000000007;

    void set_mod(int mod)
    {
        MOD = mod;
    }

    class Mint
    {
    public:
        int val;

        Mint(long long v = 0)
        {
            if (v >= 0)
            {
                if (v < MOD)
                    val = v;
                else
                    val = v % MOD;
            }
            else
            {
                if (v >= -MOD)
                {
                    val = v + MOD;
                }
                else
                {
                    v %= MOD;
                    if (v < 0)
                        v += MOD;
                    val = v;
                }
            }
        }

        Mint &operator+=(const Mint &other)
        {
            val += other.val;
            if (val >= MOD)
                val -= MOD;
            return *this;
        }

        Mint &operator-=(const Mint &other)
        {
            val -= other.val;
            if (val < 0)
                val += MOD;
            return *this;
        }

        static unsigned fast_mod(uint64_t x, unsigned m = MOD)
        {
#if !defined(_WIN32) || defined(_WIN64)
            return x % m;
#endif
            
            unsigned x_high = x >> 32, x_low = (unsigned)x;
            unsigned quot, rem;
            asm("divl %4\n"
                : "=a"(quot), "=d"(rem)
                : "d"(x_high), "a"(x_low), "r"(m));
            return rem;
        }

        Mint &operator*=(const Mint &other)
        {
            val = fast_mod((uint64_t)val * other.val);
            return *this;
        }

        friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; }
        friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; }
        friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; }
        
        friend std::ostream &operator<<(std::ostream &stream, const Mint &m)
        {
            return stream << m.val;
        }

    };
 
    std::vector<Mint> inv = {0, 1}, factorial = {1, 1}, inv_factorial = {1, 1};

    void prepare_factorials(int maximum)
    {
        factorial.resize(maximum + 1);
        inv.resize(maximum + 1);
        inv_factorial.resize(maximum + 1);

        for (int p = 2; p * p <= MOD; p++)
            asl_assert(MOD % p != 0);

        for (int i = 2; i <= maximum; ++i)
        {
            factorial[i] = i * factorial[i - 1];
            inv[i] = inv[MOD % i] * (MOD - MOD / i);
            inv_factorial[i] = inv[i] * inv_factorial[i - 1];
        }
    }

#include <random>

#include <utility>

    template <class Fun>
    class y_combinator_result
    {
        Fun fun_;

    public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&... args)
        {
            return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
    };

    template <class Fun>
    decltype(auto) y_combinator(Fun &&fun)
    {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
    }

} 

#define endl '\n'

using namespace std;
using namespace asl;

class STP {
    class Node {
    public:
        Mint sum;
        int left, right;
    };
public:

    vector<Node> node;
    int root;

    STP(int n) : node(0) {
        root = build(0, n);
    }

    int new_node(int s=0) {
        node.push_back({ Mint(s), 0, 0 });
        return node.size() - 1;
    }

    int build(int b, int e) {
        auto root = new_node();

        if (b + 1 < e) {
            int m = (b + e) >> 1;
            auto le = build(b, m);
            auto ri = build(m, e);

            node[root].left = le;
            node[root].right = ri;
        }

        return root;
    }

    int clone(int u) {
        auto cur = node[u];
        node.push_back(cur);
        return node.size() - 1;
    }

    int update(int root, int b, int e, int x, Mint v) {
        root = clone(root);

        if (b + 1 == e) {
            node[root].sum = v;
        }
        else {
            int m = (b + e) >> 1;
            if (x < m) {
                auto le = update(node[root].left, b, m, x, v);
                node[root].left = le;
            }
            else {
                auto ri = update(node[root].right, m, e, x, v);
                node[root].right = ri;
            }

            node[root].sum = node[node[root].left].sum + node[node[root].right].sum;
        }

        return root;
    }

    Mint query(int root, int b, int e, int x, int y) {
        if (x <= b&& e <= y) {
            return node[root].sum;
        }
        else {
            int m = (b + e) >> 1;

            Mint res;

            if (x < m) res += query(node[root].left, b, m, x, y);
            if (m < y) res += query(node[root].right, m, e, x, y);

            return res;
        }
    }
};

pair<int, int> get_interval(int root, int h, int x, int delta) {
    int b = root << h;
    int e = b + (1 << h);

    if (x < (b + e) / 2) {
        b += (1 << (h - 1));
    }
    else {
        e -= (1 << (h - 1));
    }

    return { b - delta, e - delta };
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    set_mod(m1000000007);

    int h; cin >> h;
    int l = (1 << (h -1));
    prepare_factorials(4 * l);

    vec<int> P(l);
    cin >> P;
    for (auto &x : P)
        --x;

    vec<Mint> acc(l);
    vec<Mint> curi(1 << h);
    curi[0] = 1;

    auto dfs = y_combinator([&](auto self, int s, Mint v, Mint i) -> void {
        curi[s] = i;

        if (s >= l) {
            acc[s - l] = v;
        }
        else {
            self(2 * s, v * 2 * s, i * inv[2 * s]);
            self(2 * s + 1, v * (2 * s + 1), i * inv[2 * s + 1]);
        }
        });

    dfs(1, 1, 1);

    STP st(l);

    vector<int> roots ={ st.root };

    for (int i = 0; i < l; ++i) {
        int r = roots.back();
        r = st.update(r, 0, l, P[i], acc[i] * acc[P[i]]);
        roots.push_back(r);
    }

    auto query = [&](int b1, int e1, int b2, int e2) {
        
        auto ans = st.query(roots[e1], 0, l, b2, e2) - st.query(roots[b1], 0, l, b2, e2);
        
        return ans;
    };

    Mint fin = 0;

    for (int i = 0; i < l; ++i) {
        int u = l + i;
        int v = l + P[i];

        int tu = u;

        Mint pp = 0;
        for (int a = 1; a < h; ++a) {
            tu /= 2;
            auto iu = get_interval(tu, a, u, l);

            int tv = v;
            for (int b = 1; b < h; ++b) {
                tv /= 2;
                auto iv = get_interval(tv, b, v, l);

                auto cur = query(iu.first, iu.second, iv.first, iv.second);

                pp += curi[tu / 2] * curi[tu / 2] * curi[tv / 2] * curi[tv / 2] * cur * inv[tu] * inv[tv];
            }
        }

        fin += pp * acc[u - l] * acc[v - l];
    }

    cout << fin * inv[2] << endl;

    return 0;
}




Compiler output:
In file included from /usr/include/c++/14/random:48,
                 from a.cc:160:
/usr/include/c++/14/bits/random.h:72:33: error: 'numeric_limits' is not a member of 'asl::std'; did you mean 'std::numeric_limits'?
   72 |                           (std::numeric_limits<_UIntType>::digits)>
      |                                 ^~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/chrono.h:39,
                 from /usr/include/c++/14/chrono:41,
                 from a.cc:5:
/usr/include/c++/14/limits:312:12: note: 'std::numeric_limits' declared here
  312 |     struct numeric_limits : public __numeric_limits_base
      |            ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/random.h:72:57: error: expected primary-expression before '>' token
   72 |                           (std::numeric_limits<_UIntType>::digits)>
      |                                                         ^
/usr/include/c++/14/bits/random.h:72:60: error: '::digits' has not been declared
   72 |                           (std::numeric_limits<_UIntType>::digits)>
      |                                                            ^~~~~~
/usr/include/c++/14/bits/random.h: In static member function 'static _Tp asl::std::__detail::_Mod<_Tp, __m, __a, __c, __big_enough, __schrage_ok>::__calc(_Tp)':
/usr/include/c++/14/bits/random.h:223:50: error: '__lg' is not a member of 'asl::std'; did you mean 'std::__lg'?
  223 |             = typename _Select_uint_least_t<std::__lg(__a)
      |                                                  ^~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:1547:5: note: 'std::__lg' declared here
 1547 |     __lg(_Tp __n)
      |     ^~~~
/usr/include/c++/14/bits/random.h:224:52: error: '__lg' is not a member of 'asl::std'; did you mean 'std::__lg'?
  224 |                                             + std::__lg(__m) + 2>::type;
      |                                                    ^~~~
/usr/include/c++/14/bits/stl_algobase.h:1547:5: note: 'std::__lg' declared here
 1547 |     __lg(_Tp __n)
      |     ^~~~
/usr/include/c++/14/bits/random.h:224:65: error: template argument 1 is invalid
  224 |                                             + std::__lg(__m) + 2>::type;
      |                                                                 ^
/usr/include/c++/14/bits/random.h:224:65: error: template argument 2 is invalid
/usr/include/c++/14/bits/random.h: At global scope:
/usr/include/c++/14/bits/random.h:270:28: error: 'is_floating_point' is not a member of 'asl::std'; did you mean 'std::is_floating_point'?
  270 |         static_assert(std::is_floating_point<_DInputType>::value,
      |                            ^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:521:12: note: 'std::is_floating_point' declared here
  521 |     struct is_floating_point
      |            ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/random.h:270:57: error: expected primary-expression before '>' token
  270 |         static_assert(std::is_floating_point<_DInputType>::value,
      |                                                         ^
/usr/include/c++/14/bits/random.h:270:60: error: '::value' has not been declared
  270 |         static_assert(std::is_floating_point<_DInputType>::value,
      |                                                            ^~~~~
/usr/include/c++/14/bits/random.h: In member function '_DInputType asl::std::__detail::_Adaptor<_Engine, _DInputType>::operator()()':
/usr/include/c++/14/bits/random.h:294:42: error: 'numeric_limits' is not a member of 'asl::std'; did you mean 'std::numeric_limits'?
  294 |                                     std::numeric_limits<_DInputType>::digits,
      |                                          ^~~~~~~~~~~~~~
/usr/include/c++/14/limits:312:12: note: 'std::numeric_limits' declared here
  312 |     struct numeric_limits : public __numeric_limits_base
      |            ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/random.h:293:23: error: parse error in template argument list
  293 |           return std::generate_canonical<_DInputType,
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  294 |                                     std::numeric_limits<_DInputType>::digits,
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/random.h:293:23: error: function template-id 'generate_canonical<_DInputType, <expression error> >' in nested-name-specifier
/usr/include/c++/14/bits/random.h:61:5: note: 'template<class _RealType, long unsigned int __bits, class _UniformRandomNumberGenerator> _RealType asl::std::generate_canonical(_UniformRandomNumberGenerator&)' declared here
   61 |     generate_canonical(_UniformRandomNumberGenerator& __g);
      |     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/random.h:295:44: error: expected primary-expression before '>' token
  295 |                                     _Engine>(_M_g);
      |                                            ^
/usr/include/c++/14/bits/random.h: At global scope:
/usr/include/c++/14/bits/random.h:309:16: error: 'declval' is not a member of 'asl::std'; did you mean 'std::declval'?
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                ^~~~~~~
/usr/include/c++/14/type_traits:2485:10: note: 'std::declval' declared here
 2485 |     auto declval() noexcept -> decltype(__declval<_Tp>(0))
      |          ^~~~~~~
/usr/include/c++/14/bits/random.h:309:16: error: 'declval' is not a member of 'asl::std'; did you mean 'std::declval'?
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                ^~~~~~~
/usr/include/c++/14/type_traits:2485:10: note: 'std::declval' declared here
 2485 |     auto declval() noexcept -> decltype(__declval<_Tp>(0))
      |          ^~~~~~~
/usr/include/c++/14/bits/random.h:309:29: error: expected primary-expression before '&' token
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                             ^
/usr/include/c++/14/bits/random.h:309:30: error: expected primary-expression before '>' token
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                              ^
/usr/include/c++/14/bits/random.h:309:32: error: expected primary-expression before ')' token
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                                ^
/usr/include/c++/14/bits/random.h:309:48: error: 'declval' is not a member of 'asl::std'; did you mean 'std::declval'?
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                                                ^~~~~~~
/usr/include/c++/14/type_traits:2485:10: note: 'std::declval' declared here
 2485 |     auto declval() noexcept -> decltype(__declval<_Tp>(0))
      |          ^~~~~~~
/usr/include/c++/14/bits/random.h:309:70: error: expected primary-expression before '*' token
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                                                                      ^
/usr/include/c++/14/bits/random.h:309:71: error: expected primary-expression before '>' token
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                                                                       ^
/usr/include/c++/14/bits/random.h:309:73: error: expected primary-expression before ')' token
  309 |           std::declval<_Sseq&>().generate(std::declval<uint_least32_t*>(),
      |                                                                         ^
/usr/include/c++/14/bits/random.h:310:48: error: 'declval' is not a member of 'asl::std'; did you mean 'std::declval'?
  310 |                                           std::declval<uint_least32_t*>()));
      |                                                ^~~~~~~
/usr/include/c++/14/type_traits:2485:10: note: 'std::declval' declared here
 2485 |     auto declval() noexcept -> decltype(__declval<_Tp>(0))
      |          ^~~~~~~
/usr/include/c++/14/bits/random.h:310:70: error: expected primary-expression before '*' token
  310 |                                           std::declval<uint_least32_t*>()));
      |                                                                      ^
/usr/include/c++/14/bits/random.h:310:71: error: expected primary-expression before '>' token
  310 |                                           std::declval<uint_least32_t*>()));
      |                                                                       ^
/usr/include/c++/14/bits/random.h:310:73: error: expected primary-expression before ')' token
  310 |                                           std::declval<uint_least32_t*>()));
      |                                                                         ^
/usr/include/c++/14/bits/random.h:313:40: error: '__seed_seq_generate_t' does not name a type
  313 |              typename _GenerateCheck = __seed_seq_generate_t<_Sseq>>
      |                                        ^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/random.h:313:61: error: expected '>' before '<' token
  313 |              typename _GenerateCheck = __seed_seq_generate_t<_Sseq>>
      |                                                             ^
/usr/include/c++/14/bits/random.h:314:32: error: '_Require' does not name a type
  314 |       using _If_seed_seq_for = _Require<
      |                                ^~~~~~~~
/usr/include/c++/14/bits/random.h:368:26: error: 'is_unsigned' is not a member of 'asl::std'; did you mean 'std::is_unsigned'?
  368 |       static_assert(std::is_unsigned<_UIntType>::value,
      |                          ^~~~~~~~~~~
/usr/include/c++/14/type_traits:958:12: note: 'std::is_unsigned' declared here
  958 |     struct is_unsigned
      |            ^~~~~~~~~~~
/usr/include/c++/14/bits/random.h:368:47: error: expected primary-expression before '>' token
  368 |       static_assert(std::is_unsigned<_UIntTy