Source Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template <class __set_element_type>
using gnu_set = tree<__set_element_type, null_type, less<__set_element_type>, rb_tree_tag, tree_order_statistics_node_update>;
template <class __key_type, class __val_type>
using gnu_map = tree<__key_type, __val_type, less<__key_type>, rb_tree_tag, tree_order_statistics_node_update>;

#define ios                  \
    ios::sync_with_stdio(0); \
    cin.tie(0)

const ll oo = 1e18;
const ll MOD = 1e9 + 7;

int n;

vector<ll> perm(int(2e6) + 5);

void process() {
    ll mul = 1;
    perm[0] = 1;
    for (ll i = 1; i <= ll(2e6) + 1; i++)
        perm[i] = (perm[i - 1] * i) % MOD;
}

ll binpow(ll a, ll b) {
    a %= MOD;
    ll res = 1;
    while (b > 0) {
        if (b % 2 != 0)
            res = res * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return res;
}

ll divide(ll a, ll b) {
    return a * binpow(b, MOD - 2) % MOD;
}

int main() {
    ios;
    cin >> n;
    vector<ll> P(n), Q(n);
    for (auto &p : P)
        cin >> p;
    for (auto &q : Q)
        cin >> q;

    vector<ll> steps(n);
    for (int i = 0; i < n; i++) {
        if (Q[i] < P[i] || (Q[i] - P[i]) % (i + 1) != 0) {
            cout << "0";
            return 0;
        }
        steps[i] = (Q[i] - P[i]) / (i + 1);
    }
    process();
    ll result = 0;
    for (auto step : steps)
        result += step;
    result = perm[result];
    for(auto step: steps)
        result = divide(result, perm[step]);
    cout << result;
    return 0;
}
Copy
N-dimensions Ammar Abu Yaman
GNU G++17
188 ms
20.7 MB
Runtime Error