Proficient.
Put your skills to the test.

Problem summary

Count sequences of distinct nonnegative integer-coordinate points (x[i],y[i]) satisfying x[i]+y[i]=a[i], nondecreasing x, and nonincreasing y. Return the count modulo 123456789. Adjacent a values are different.

Constraints

1 ≤ n ≤ 10000; 0 ≤ a[i] ≤ 10000; a[i]≠a[i+1].

Worked example

Original statement sample.

3
4 5 3

10

Solution analysis

1. Eliminate y using y[i]=a[i]−x[i]. The two monotonicity conditions together require x[i+1]−x[i]≥max(0,a[i+1]−a[i]). Let S[i] be the sum of these forced positive rises before position i, and write b[i]=x[i]−S[i]. Then b is simply nondecreasing.
2. The upper bounds a[i]−S[i] never increase: a rise leaves this bound unchanged and a drop decreases it. Therefore every b must lie between 0 and the final bound B=a[n]−S[n]. Equivalently, start B=a[1] and subtract every positive drop a[i]−a[i+1]. If B<0 no sequence exists.
3. Counting 0≤b[1]≤…≤b[n]≤B is a standard stars-and-bars problem. The n+1 gaps b[1],b[2]−b[1],…,b[n]−b[n−1],B−b[n] are nonnegative and sum to B, giving C(n+B,n). For [4,5,3], S is [0,1,1], so B=2 and the answer is C(5,3)=10.
4. The modulus is composite, so factorial denominators cannot generally be inverted modulo it. Instead sieve primes up to n+B≤20000, find each prime’s exponent in (n+B)!−n!−B! using repeated division, and multiply those prime powers modulo 123456789. This performs exact integer cancellation before reduction.

Why it works

The change of variables is a bijection: monotone b values in [0,B] produce nonnegative x=b+S and y=a−S−b with the required coordinate orders, and every valid point sequence yields such a b sequence. Since adjacent a values differ, adjacent points cannot coincide; monotonicity then also prevents any repeated nonadjacent point. Stars and bars counts the b sequences, and factorial prime exponents compute the resulting binomial coefficient exactly modulo the composite modulus.

Watch out. Do not use Fermat inverses with this composite modulus. A negative final bound means zero ways. Equal coordinates are allowed, but identical points are not; the promise that adjacent a values differ is essential to the simple formula. Reduce 64-bit products modulo the modulus.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
const long long MOD=123456789;
int factorialExponent(int n,int prime){
    int exponent=0;
    while(n>0){
        n/=prime;
        exponent+=n;
    }
    return exponent;
}
long long powerModulo(long long base,int exponent){
    long long result=1;
    while(exponent>0){
        if(exponent%2==1){
            result=result*base%MOD;
        }
        base=base*base%MOD;
        exponent/=2;
    }
    return result;
}
int main(){
    int n;
    cin>>n;
    int previous;
    cin>>previous;
    int bound=previous;
    for(int i=1;i<n;i++){
        int current;
        cin>>current;
        if(previous>current){
            bound-=previous-current;
        }
        previous=current;
    }
    if(bound<0){
        cout<<0<<'\n';
        return 0;
    }
    int total=n+bound;
    vector<bool>prime(total+1,true);
    prime[0]=false;
    prime[1]=false;
    long long answer=1;
    for(int p=2;p<=total;p++){
        if(!prime[p]){
            continue;
        }
        if(p<=total/p){
            for(int multiple=p*p;multiple<=total;multiple+=p){
                prime[multiple]=false;
            }
        }
        // Cancel factorials in integer prime exponents, not by modular division.
        int exponent=factorialExponent(total,p)-factorialExponent(n,p)-factorialExponent(bound,p);
        answer=answer*powerModulo(p,exponent)%MOD;
    }
    cout<<answer<<'\n';
}