Binary tree

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <unordered_map>

using namespace std;

const long long mod = (long long) 1e9 + 7;

int n, m;

long long fp(long long a, long long b) {
  long long ans = 1;
  a %= mod;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    b >>= 1;
    a = (a * a) % mod;
  }
  return ans;
}

pair <int, int> level(long long x) {
  int ans = 1;
  int t = 1;
  while (x != 1) {
    ans++;
    if (x == 2) {
      t = 1;
    } else if (x == 3) {
      t = 2;
    }
    x >>= 1;
  }
  return make_pair(n - ans + 1, t);
}

string tobin(long long x) {
  string ans;
  while (x > 0) {
    if (x & 1) {
      ans = '1' + ans;
    } else {
      ans = '0' + ans;
    }
    x >>= 1;
  }
  return ans;
}

int main() {
  cin >> n >> m;
  vector <long long> ve;
  set <long long> se;
  for (int i = 0; i < m; i++) {
    long long x;
    cin >> x;
    //ve.push_back(x);
    se.insert(x);
  }
  //sort(ve.begin(), ve.end());
  vector <long long> vecc;
  while (!se.empty()) {
    long long tmp = *(--se.end());
    long long lst = tmp;
    while (!se.empty() && (tmp >> 1) >= *se.begin()) {
      tmp >>= 1;
      if (se.count(tmp)) {
        se.erase(lst);
        lst = tmp;
      }
    }
    vecc.push_back(lst);
    se.erase(lst);
  }
  long long lef = fp(2, n - 2), rig = fp(2, n - 2);
  for (long long v : vecc) {
    pair <int, int> here = level(v);
    if (here.second == 1) {
      lef -= fp(2, here.first - 1);
      lef %= mod;
      lef += mod;
      lef %= mod;
    } else {
      rig -= fp(2, here.first - 1);
      rig %= mod;
      rig += mod;
      rig %= mod;
    }
  }
  cout << (lef * rig * 2) % mod << endl;
  return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: WRONG ANSWER

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: WRONG ANSWER

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: WRONG ANSWER

Test 14

Group: 1

Verdict: WRONG ANSWER

Test 15

Group: 1

Verdict: WRONG ANSWER

Test 16

Group: 1

Verdict: WRONG ANSWER

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: WRONG ANSWER

Test 20

Group: 1

Verdict: WRONG ANSWER

Test 21

Group: 1

Verdict: WRONG ANSWER

Test 22

Group: 1

Verdict: ACCEPTED

Test 23

Group: 1

Verdict: ACCEPTED

Test 24

Group: 1

Verdict: ACCEPTED

Test 25

Group: 1

Verdict: ACCEPTED

Test 26

Group: 1

Verdict: ACCEPTED

Test 27

Group: 1

Verdict: ACCEPTED

Test 28

Group: 1

Verdict: ACCEPTED

Test 29

Group: 1

Verdict: ACCEPTED

Test 30

Group: 1

Verdict: ACCEPTED

Test 31

Group: 1

Verdict: ACCEPTED

Test 32

Group: 1

Verdict: ACCEPTED

Test 33

Group: 1

Verdict: ACCEPTED

Test 34

Group: 1

Verdict: ACCEPTED

Test 35

Group: 1

Verdict: ACCEPTED

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: ACCEPTED

Test 38

Group: 2

Verdict: ACCEPTED

Test 39

Group: 2

Verdict: ACCEPTED

Test 40

Group: 2

Verdict: ACCEPTED

Test 41

Group: 2

Verdict: ACCEPTED

Test 42

Group: 2

Verdict: ACCEPTED

Test 43

Group: 2

Verdict: ACCEPTED

Test 44

Group: 2

Verdict: ACCEPTED

Test 45

Group: 2

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED

Test 55

Group: 3

Verdict: ACCEPTED

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: ACCEPTED

Test 58

Group: 3

Verdict: ACCEPTED

Test 59

Group: 3

Verdict: ACCEPTED

Test 60

Group: 3

Verdict: ACCEPTED

Test 61

Group: 3

Verdict: WRONG ANSWER

Test 62

Group: 3

Verdict: ACCEPTED

Test 63

Group: 3

Verdict: WRONG ANSWER

Test 64

Group: 3

Verdict: ACCEPTED

Test 65

Group: 3

Verdict: WRONG ANSWER

Test 66

Group: 3

Verdict: ACCEPTED

Test 67

Group: 3

Verdict: ACCEPTED

Test 68

Group: 3

Verdict: ACCEPTED

Test 69

Group: 3

Verdict: ACCEPTED

Test 70

Group: 3

Verdict: ACCEPTED

Test 71

Group: 3

Verdict: ACCEPTED

Test 72

Group: 3

Verdict: ACCEPTED

Test 73

Group: 3

Verdict: ACCEPTED

Test 74

Group: 3

Verdict: ACCEPTED

Test 75

Group: 3

Verdict: ACCEPTED

Test 76

Group: 3

Verdict: ACCEPTED

Test 77

Group: 3

Verdict: ACCEPTED