#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

const int MAXN = 1000010;
const ll MOD = 1e9 + 7;
const ll pr = 37;

vector<bool> prime (MAXN, true);

vector<ll> p;

ll modul(ll x) {
    return (x + MOD + MOD) % MOD;
}

void precalc() {
    p[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        p[i] = modul(p[i - 1] * pr);
    }
}

struct Node{
    Node *left, *right;
    ll hash;
    ll prior;
    int mult;
    int sz;
    char symbol;
    Node(){}
    Node(int new_val = 0, char new_symbol = 0) {
        sz = 1;
        prior = rand();
        left = right = nullptr;
        hash = new_symbol;
        symbol = new_symbol;
        mult = 0;
    }
};

int safe_get_size(Node *root) {
    if (root) {
        return root->sz;
    } else {
        return 0;
    }
}

int safe_get_hash(Node *root) {
    if (root) {
        return root->hash;
    } else {
        return 0;
    }
}

void relax(Node *root) {
    if (!root) {
        return;
    } else {
        root->sz = safe_get_size(root->left) + safe_get_size(root->right) + 1;
        ll left_hash = safe_get_hash(root->left);
        ll right_hash = safe_get_hash(root->right);
        root->hash = modul(left_hash + modul(right_hash * p[safe_get_size(root->left)]));
    }
}


void push(Node *root) {
    if (!root || !root->mult)
        return;
    if (root->left) {
        root->left->mult += root->mult;
    }
    if (root->right) {
        root->right->mult += root->mult;
    }
    root->hash = modul(root->hash * p[root->mult]);
    root->mult = 0;
}

pair<Node*, Node*> split(Node *root, int k) {
    push(root);
    if (!root) {
        return {nullptr, nullptr};
    }
    if (safe_get_size(root->left) >= k) {
        auto p = split(root->left, k);
        root->left = p.second;
        relax(root);
        return {p.first, root};
    } else {
        auto p = split(root->right, k - safe_get_size(root->left) - 1);
        root->right = p.first;
        relax(root);
        return {root, p.second};
    }
}

Node *merge(Node *L, Node *R) {
    push(L);
    push(R);
    if (!L) {
        return R;
    }
    if (!R) {
        return L;
    }
    if (L->prior < R->prior) {
        L->right = merge(L->right, R);
        relax(L);
        return L;
    } else {
        R->left = merge(L, R->left);
        relax(R);
        return R;
    }
}

Node *add(Node *root, ) {

}

int main() {
//    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n = MAXN - 1;
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (prime[i]) {
            if (i * 1ll * i <= n) {
                for (int j = i * i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
    return 0;
}