Overview

In each step, we place \(1\) block at a time, and we want to find the number of operation sequences such that there are always \(K\) or more towers visible from the left.

The key point is that after the very first step, there is always exactly \(1\) visible tower, so if \(K > 1\), it is always impossible.

Analysis

Initially, the height of all towers is \(0\).

Let’s consider the first step.
Since we place \(1\) block on one of the towers, there is exactly \(1\) tower with a height of \(1\) or more.

At this moment, the number of towers visible from the left is also always exactly \(1\).

Therefore, if we require at least \(K\) towers to be visible as a visibility condition:

• If \(K > 1\)
  The condition cannot be satisfied immediately after the first step, so the answer is \(0\).
• If \(K = 1\)
  Since there is always at least one tower with a positive height after each step, at least \(1\) tower is always visible.

If \(K = 1\), the condition is satisfied regardless of the order in which we stack the blocks.

This is because, in any state where at least \(1\) block has been placed, the first tower from the left with a positive height is always visible.

For example, if the heights are

\(0, 0, 3, 1\)

the \(3\)rd tower is visible because all towers to its left have height \(0\).

Therefore, for \(K = 1\), we just need to count the total number of orders to stack the specified number of blocks on each tower.

Let the total number of blocks be

\(S = H_1 + H_2 + \cdots + H_N\)

There are \(S\) steps in total, and among them, the step of stacking a block on tower \(i\) occurs exactly \(H_i\) times.

Therefore, the number of operation sequences is given by the multinomial coefficient:

\(\displaystyle \frac{S!}{H_1! H_2! \cdots H_N!}\)

For example, if \(H = [2, 1]\), there are \(3\) steps in total:

• The operation of stacking on tower \(1\) occurs \(2\) times.
• The operation of stacking on tower \(2\) occurs \(1\) time.

So the possible sequences are:

• \(1, 1, 2\)
• \(1, 2, 1\)
• \(2, 1, 1\)

which gives \(3\) ways.

This matches

\(\displaystyle \frac{3!}{2!1!} = 3\)

Algorithm

1. Input \(N, K\) and each \(H_i\).
2. Calculate \(S = \sum H_i\).
3. If \(K > 1\), output \(0\) because the condition cannot be satisfied immediately after the first step.
4. If \(K = 1\), the answer is

\(\displaystyle \frac{S!}{H_1! H_2! \cdots H_N!}\)

1. Since the division is performed modulo \(10^9+7\), precompute factorials and inverse factorials.
2. Calculate the answer as

\(\displaystyle S! \times (H_1!)^{-1} \times (H_2!)^{-1} \times \cdots \times (H_N!)^{-1}\)

Since the modulo \(10^9+7\) is a prime number, we can find the modular inverse using Fermat’s Little Theorem:

\(\displaystyle a^{-1} \equiv a^{MOD-2} \pmod{MOD}\)

Complexity

• Time Complexity: \(O(S + \log MOD)\)
• Space Complexity: \(O(S)\)

where \(S = \sum_{i=1}^{N} H_i\).

Implementation Details

Prepare the factorials fact and inverse factorials invfact.

First, compute

fact[i] = i!

from \(0\) to \(S\).

Next, find

invfact[S] = (S!)^{-1}

using fast exponentiation, and then compute the inverse factorials in reverse order as

invfact[i - 1] = invfact[i] * i

Finally, we can calculate the multinomial coefficient

\(\displaystyle \frac{S!}{H_1! H_2! \cdots H_N!}\)

by doing:

ans = fact[S];
for (int h : H) {
    ans = ans * invfact[h] % MOD;
}

Source Code

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

long long modpow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<int> H(N);
    int S = 0;
    for (int i = 0; i < N; i++) {
        cin >> H[i];
        S += H[i];
    }

    if (K > 1) {
        cout << 0 << '\n';
        return 0;
    }

    vector<long long> fact(S + 1), invfact(S + 1);
    fact[0] = 1;
    for (int i = 1; i <= S; i++) fact[i] = fact[i - 1] * i % MOD;

    invfact[S] = modpow(fact[S], MOD - 2);
    for (int i = S; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;

    long long ans = fact[S];
    for (int h : H) {
        ans = ans * invfact[h] % MOD;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.