OI XXVII - czw

// https://szkopul.edu.pl/problemset/problem/GcP-wwgKv1HiCzuFRKE6n7-U/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

int m;

constexpr int sizik = 1000 * 1001;

std::vector<int> kra[sizik];

namespace Trie_DS {

struct __attribute__((packed)) Trie {
    int32_t next[2]{0, 0};
    bool v;
    int32_t val1 = 0;
    int32_t val2 = 0;
    Trie(bool z) : v(z) { ; }
};

std::vector<Trie> Trie_X, Trie_Y;

} // namespace Trie_DS

std::vector<int> black_nodes;

namespace DSU {

int rep[sizik];
std::vector<int> sz[sizik];
int sz2[sizik];
void init(int n) {
    for (int i = 0; i <= n; i++) {
        rep[i] = i;
        sz2[i] = 1;
    }
}
int Find(int a) {
    return rep[a] == a ? a : rep[a] = Find(rep[a]);
}
void merge(std::vector<int>& tom, std::vector<int>& from) {
    if (tom.size() < from.size()) std::swap(tom, from);
    tom.insert(tom.end(), from.begin(), from.end());
    from.clear();
    from.shrink_to_fit();
}
void Union(int a, int b) {
    a = Find(a), b = Find(b);
    if (a == b) return;
    if (sz2[a] > sz2[b]) std::swap(a, b);
    rep[a] = b;
    merge(sz[b], sz[a]);
    sz2[b] += sz2[a];
}

} // namespace DSU

std::string s;

char znak[sizik];
int aktp = 0, aktv = 0;

void Dfs(int v, int d) {
    assert(d >= 0);
    znak[v] = s[aktp++];
    if (znak[v] == '0') return;
    if (znak[v] == '1') {
        DSU::sz[v] = {2 * d};
        black_nodes.push_back(v);
        return;
    }
    for (int i = 0; i < 4; i++) {
        kra[v].push_back(aktv);
        Dfs(aktv++, d - 1);
    }
}

void dfs(int v, int id, std::vector<Trie_DS::Trie>& trie, bool x) {
    if (znak[v] == '0' || znak[v] == '1') {
        return;
    }

    int id0, id1;
    if (trie[id].next[0] == 0) {
        id0 = trie.size();
        id1 = id0 + 1;
        trie.push_back({0});
        trie.push_back({1});
        trie[id].next[0] = id0;
        trie[id].next[1] = id1;
    } else {
        id0 = trie[id].next[0];
        id1 = trie[id].next[1];
    }

    if (x) {
        dfs(kra[v][0], id0, trie, x);
        dfs(kra[v][2], id0, trie, x);
        dfs(kra[v][1], id1, trie, x);
        dfs(kra[v][3], id1, trie, x);
    } else {
        dfs(kra[v][2], id0, trie, x);
        dfs(kra[v][3], id0, trie, x);
        dfs(kra[v][0], id1, trie, x);
        dfs(kra[v][1], id1, trie, x);
    }
}

int h = 0;
void DFs(int v, std::vector<Trie_DS::Trie>& trie) {
    bool leaf = trie[v].next[0] == 0;
    if (leaf) {
        trie[v].val1 = ++h;
    } else {
        DFs(trie[v].next[0], trie);
        DFs(trie[v].next[1], trie);
        trie[v].val1 = trie[trie[v].next[1]].val1;
    }
}

void DFS(int v, std::vector<Trie_DS::Trie>& trie, int val) {
    bool leaf = trie[v].next[0] == 0;
    trie[v].val2 = val;
    if (!leaf) {
        DFS(trie[v].next[0], trie, val);
        DFS(trie[v].next[1], trie, trie[trie[v].next[0]].val1);
    }
}

constexpr int START = +1, END = -1;
struct Event {
    int x;
    int type;
    int y_min;
    int y_max;
    int id;

    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type > other.type;
    }
};
std::vector<Event> events;

struct C {
    int y1 = -1, y2 = -1;
    C(int y3 = -1, int y4 = -1) : y1(y3), y2(y4) {}
};
C ziomki[sizik];
int max_y_coord;
void _Dfs(int v, int d, int id_x, int id_y) {
    assert(d >= 0);
    if (znak[v] == '0') return;
    if (znak[v] == '1') {
        ziomki[v].y2 = Trie_DS::Trie_Y[id_y].val1;
        ziomki[v].y1 = Trie_DS::Trie_Y[id_y].val2;
        if (ziomki[v].y1 > ziomki[v].y2) {
            std::swap(ziomki[v].y1, ziomki[v].y2);
        }
        max_y_coord = std::max(max_y_coord, ziomki[v].y2);
        assert(Trie_DS::Trie_X[id_x].val2 <= Trie_DS::Trie_X[id_x].val1);
        events.push_back({Trie_DS::Trie_X[id_x].val2, START, ziomki[v].y1, ziomki[v].y2, v});
        events.push_back({Trie_DS::Trie_X[id_x].val1, END, ziomki[v].y1, ziomki[v].y2, v});

        return;
    }
    assert(kra[v].size() == 4);
    _Dfs(kra[v][0], d - 1, Trie_DS::Trie_X[id_x].next[0], Trie_DS::Trie_Y[id_y].next[1]);
    _Dfs(kra[v][1], d - 1, Trie_DS::Trie_X[id_x].next[1], Trie_DS::Trie_Y[id_y].next[1]);
    _Dfs(kra[v][2], d - 1, Trie_DS::Trie_X[id_x].next[0], Trie_DS::Trie_Y[id_y].next[0]);
    _Dfs(kra[v][3], d - 1, Trie_DS::Trie_X[id_x].next[1], Trie_DS::Trie_Y[id_y].next[0]);
}

namespace SegTree {

int tree[4 * sizik];
int lazy[4 * sizik];

void init() {
    std::memset(tree, -1, sizeof(tree));
    std::memset(lazy, -2, sizeof(lazy));
}

void push(int node) {
    if (lazy[node] != -2) {
        tree[2 * node] = lazy[node];
        lazy[2 * node] = lazy[node];
        tree[2 * node + 1] = lazy[node];
        lazy[2 * node + 1] = lazy[node];
        lazy[node] = -2;
    }
}

void update(int v, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (l == tl && r == tr) {
        tree[v] = val;
        lazy[v] = val;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, std::min(r, tm), val);
        update(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, val);

        if (tree[2 * v] == tree[2 * v + 1]) {
            tree[v] = tree[2 * v];
        } else {
            tree[v] = -3;
        }
    }
}

void query_and_merge(int v, int tl, int tr, int l, int r, int rectID) {
    if (l > r) return;

    if (tree[v] >= 0) {
        DSU::Union(rectID, tree[v]);
        return;
    }

    if (tree[v] == -1) return;

    if (tl == tr) return;

    push(v);
    int tm = (tl + tr) / 2;
    query_and_merge(2 * v, tl, tm, l, std::min(r, tm), rectID);
    query_and_merge(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, rectID);
}

} // namespace SegTree

void normalize(std::map<int, int>& mp) {
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        if (it->second >= 2) {
            mp[it->first + 1] += it->second >> 1;
            it->second &= 1;
        }
    }
    auto it = mp.begin();
    while (it != mp.end()) {
        if (it->second == 0)
            it = mp.erase(it);
        else
            ++it;
    }
}

// true if A < B
bool is_smaller(const std::map<int, int>& countA, const std::map<int, int>& countB) {
    if (countA.empty()) return !countB.empty();
    if (countB.empty()) return false;

    int max_pow = std::max(countA.rbegin()->first, countB.rbegin()->first);

    auto itA = countA.rbegin();
    auto itB = countB.rbegin();

    while (itA != countA.rend() && itB != countB.rend()) {
        if (itA->first != itB->first) return itA->first < itB->first;
        itA++;
        itB++;
    }
    return itA == countA.rend() && itB != countB.rend();
}

int visited[sizik];

constexpr int MOD = 1e9 + 7;

int binpow(int64_t a, int64_t b) {
    int64_t res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int calc(const std::map<int, int>& mp) {
    int wyn = 0;
    for (const auto& [a, b] : mp) {
        wyn += (b * binpow(2, a)) % MOD;
        if (wyn >= MOD) wyn -= MOD;
    }
    return wyn;
}

void solve() {
    std::cin >> m;

    for (int i = 0; i < sizik; ++i)
        kra[i].clear();
    Trie_DS::Trie_X.clear();
    Trie_DS::Trie_Y.clear();
    black_nodes.clear();
    events.clear();
    max_y_coord = 0;

    Trie_DS::Trie_X.push_back({0});
    Trie_DS::Trie_Y.push_back({0});

    std::cin >> s;
    aktv = 1;
    Dfs(0, m);

    dfs(0, 0, Trie_DS::Trie_X, 1);
    dfs(0, 0, Trie_DS::Trie_Y, 0);

    h = 0;
    DFs(0, Trie_DS::Trie_X);
    h = 0;
    DFs(0, Trie_DS::Trie_Y);

    DFS(0, Trie_DS::Trie_X, 0);
    DFS(0, Trie_DS::Trie_Y, 0);

    DSU::init(sizik - 1);

    _Dfs(0, m, 0, 0);

    std::sort(events.begin(), events.end());

    SegTree::init();

    max_y_coord += 5;
    int i = 0;
    while (i < events.size()) {
        int j = i;
        while (j < events.size() && events[j].x == events[i].x)
            j++;

        std::vector<int> starts;
        std::vector<int> ends;
        for (int k = i; k < j; ++k) {
            if (events[k].type == START)
                starts.push_back(k);
            else
                ends.push_back(k);
        }

        for (int k : starts) {
            if (events[k].y_min < events[k].y_max) SegTree::query_and_merge(1, 0, max_y_coord, events[k].y_min, events[k].y_max - 1, events[k].id);
        }

        for (int k : ends) {
            SegTree::update(1, 0, max_y_coord, events[k].y_min, events[k].y_max - 1, -1);
        }

        for (int k : starts) {
            int q_min = std::max(0, events[k].y_min - 1);
            int q_max = events[k].y_max;
            if (q_min <= q_max) SegTree::query_and_merge(1, 0, max_y_coord, q_min, q_max, events[k].id);
        }

        std::sort(starts.begin(), starts.end(), [&](int a, int b) { return events[a].y_min < events[b].y_min; });
        for (size_t k = 1; k < starts.size(); ++k) {
            if (events[starts[k]].y_min == events[starts[k - 1]].y_max) {
                DSU::Union(events[starts[k]].id, events[starts[k - 1]].id);
            }
        }

        for (int k : starts) {
            SegTree::update(1, 0, max_y_coord, events[k].y_min, events[k].y_max - 1, events[k].id);
        }

        i = j;
    }

    std::vector<int> sp;
    for (const auto& i : black_nodes) {
        if (DSU::Find(i) == i) {
            sp.push_back(i);
        }
    }

    std::vector<std::map<int, int>> normalized;
    for (const auto& x : sp) {
        std::map<int, int> mp;
        for (const auto& z : DSU::sz[x]) {
            mp[z]++;
        }
        normalize(mp);
        normalized.push_back(mp);
    }

    auto ptr = std::max_element(normalized.begin(), normalized.end(), is_smaller);
    std::cout << sp.size() << '\n';
    int ans = calc(*ptr);
    std::cout << ans << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}