Source Code
#include <bits/stdc++.h>
using namespace std;
const int N = 8e6 + 9;
const int mod = 1e9 + 7;
int extended_euclidean(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_euclidean(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
std::vector<int> invs(const std::vector<int> &a, int m) {
    int n = a.size();
    if (n == 0) return {};
    std::vector<int> b(n);
    int v = 1;
    for (int i = 0; i != n; ++i) {
        b[i] = v;
        v = static_cast<long long>(v) * a[i] % m;
    }
    int x, y;
    extended_euclidean(v, m, x, y);
    x = (x % m + m) % m;
    for (int i = n - 1; i >= 0; --i) {
        b[i] = static_cast<long long>(x) * b[i] % m;
        x = static_cast<long long>(x) * a[i] % m;
    }
    return b;
}
long long fact[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    int a[n] , b[n];
    fact[0] = fact[1] = 1;
    for(int i = 2; i < N; i++){
        fact[i] = fact[i - 1] * i;
        fact[i] %= mod;
    }
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    vector<int> arr(n);
    long long sum = 0;
    int test=  1;
    for(int i = 0; i < n; i++){
        int e =(b[i] - a[i]) / ( i + 1 );
        if(e < 0){
            test = 0;
            break;
        }
        if((b[i] - a[i]) % ( i + 1 )) test = 0;
        sum += e;
        arr[i] = fact[e];
    }
    if(test == 0){
        cout << 0 << "\n";
        return 0;
    }
    long long ans = fact[sum];
    vector<int> v = invs(arr, mod);
    for(int i = 0; i < n; i++){
        ans *= v[i];
        ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}  
Copy
N-dimensions AbduSaber
GNU G++17
242 ms
66.0 MB
Accepted