1class Solution {
2    // Maximum size for precomputed factorial arrays
3    private static final int MAX_N = 100001;
4    // Modulo value for preventing integer overflow (1e9 + 7)
5    private static final int MOD = (int) 1e9 + 7;
6    // factorial[i] stores i! % MOD
7    private static final long[] factorial = new long[MAX_N];
8    // invFactorial[i] stores the modular inverse of i! % MOD
9    private static final long[] invFactorial = new long[MAX_N];
10
11    // Static initializer: precompute factorials and their modular inverses
12    static {
13        factorial[0] = 1;
14        invFactorial[0] = 1;
15        for (int i = 1; i < MAX_N; ++i) {
16            // factorial[i] = i! = (i-1)! * i
17            factorial[i] = factorial[i - 1] * i % MOD;
18            // Modular inverse of i! via Fermat's little theorem: (i!)^(MOD-2)
19            invFactorial[i] = qmi(factorial[i], MOD - 2, MOD);
20        }
21    }
22
23    /**
24     * Fast exponentiation (quick power) under modulo.
25     * Computes (base^exponent) % mod in O(log exponent) time.
26     *
27     * @param base     the base value
28     * @param exponent the exponent
29     * @param mod      the modulo
30     * @return (base^exponent) % mod
31     */
32    public static long qmi(long base, long exponent, long mod) {
33        long result = 1;
34        while (exponent != 0) {
35            // If the current lowest bit is 1, multiply result by current base
36            if ((exponent & 1) == 1) {
37                result = result * base % mod;
38            }
39            exponent >>= 1;          // Move to the next bit
40            base = base * base % mod; // Square the base for the next bit position
41        }
42        return result;
43    }
44
45    /**
46     * Computes the binomial coefficient C(n, k) = n! / (k! * (n-k)!) under modulo.
47     *
48     * @param n total number of items
49     * @param k number of items to choose
50     * @return C(n, k) % MOD
51     */
52    public static long comb(int n, int k) {
53        // C(n, k) = n! * inverse(k!) * inverse((n-k)!)
54        return (factorial[n] * invFactorial[k] % MOD) * invFactorial[n - k] % MOD;
55    }
56
57    /**
58     * Counts the number of arrangements based on choosing elements from
59     * the left and right sides of the given position.
60     *
61     * @param n   total number of elements
62     * @param pos the reference position (0-indexed)
63     * @param k   the number of elements to select in total
64     * @return the count modulo MOD
65     */
66    public int countVisiblePeople(int n, int pos, int k) {
67        int leftCount = pos;            // Number of available elements on the left side
68        int rightCount = n - pos - 1;   // Number of available elements on the right side
69        long answer = 0;
70
71        // Iterate over how many elements 'a' to pick from the left side
72        for (int a = 0; a <= Math.min(k, leftCount); ++a) {
73            int b = k - a; // Remaining elements 'b' to pick from the right side
74
75            // Only valid if we have enough elements on the right side
76            if (b <= rightCount) {
77                // Multiply by 2 to account for symmetric (mirror) arrangements
78                answer = (answer + 2 * comb(leftCount, a) % MOD * comb(rightCount, b) % MOD) % MOD;
79            }
80        }
81        return (int) answer;
82    }
83}
84

1// Maximum size for precomputed factorial tables.
2const int kMaxN = 100001;
3// Modulus used for all arithmetic (a large prime).
4const int kMod = 1e9 + 7;
5
6// Precomputed factorials:        factorial[i]        = i! % kMod
7// Precomputed inverse factorials: invFactorial[i]    = (i!)^(-1) % kMod
8long long factorial[kMaxN];
9long long invFactorial[kMaxN];
10
11// Fast modular exponentiation: computes (base^exponent) % mod.
12long long qpow(long long base, long long exponent, long long mod) {
13    long long result = 1;
14    while (exponent != 0) {
15        // If the current lowest bit is set, multiply the result by base.
16        if ((exponent & 1) == 1) {
17            result = result * base % mod;
18        }
19        exponent >>= 1;                 // Move to the next bit.
20        base = base * base % mod;        // Square the base for the next bit.
21    }
22    return result;
23}
24
25// Static initializer that fills the factorial and inverse-factorial tables
26// once, before any Solution method is used.
27int initTables = []() {
28    factorial[0] = 1;
29    invFactorial[0] = 1;
30    for (int i = 1; i < kMaxN; ++i) {
31        // factorial[i] = factorial[i - 1] * i
32        factorial[i] = factorial[i - 1] * i % kMod;
33        // Inverse factorial via Fermat's little theorem:
34        // (i!)^(-1) = (i!)^(kMod - 2) % kMod, since kMod is prime.
35        invFactorial[i] = qpow(factorial[i], kMod - 2, kMod);
36    }
37    return 0;
38}();
39
40// Combination C(n, k) = n! / (k! * (n - k)!) computed under the modulus.
41long long comb(int n, int k) {
42    return factorial[n] * invFactorial[k] % kMod * invFactorial[n - k] % kMod;
43}
44
45class Solution {
46public:
47    int countVisiblePeople(int n, int pos, int k) {
48        // Number of people available on the left and right of pos.
49        int left = pos;
50        int right = n - pos - 1;
51        long long ans = 0;
52
53        // Choose 'a' people from the left and the remaining 'b = k - a'
54        // from the right. The factor 2 accounts for the symmetry of
55        // arranging the two chosen groups.
56        for (int a = 0; a <= min(k, left); ++a) {
57            int b = k - a;
58            if (b <= right) {
59                ans = (ans + 2 * comb(left, a) % kMod * comb(right, b) % kMod) % kMod;
60            }
61        }
62        return ans;
63    }
64};
65

1// Maximum size for precomputed factorial arrays
2const MAX_SIZE = 100001;
3
4// Modulus for preventing integer overflow (a large prime number)
5const MOD = 1000000007n;
6
7// factorials[i] stores i! mod MOD
8const factorials: bigint[] = Array(MAX_SIZE).fill(0n);
9
10// inverseFactorials[i] stores the modular inverse of i! mod MOD
11const inverseFactorials: bigint[] = Array(MAX_SIZE).fill(0n);
12
13/**
14 * Fast exponentiation: computes (base^exponent) mod modulus.
15 * Uses binary exponentiation for O(log exponent) time complexity.
16 *
17 * @param base - The base value
18 * @param exponent - The exponent value
19 * @param modulus - The modulus value
20 * @returns (base^exponent) mod modulus
21 */
22function qmi(base: bigint, exponent: bigint, modulus: bigint): bigint {
23    let result = 1n;
24    while (exponent > 0n) {
25        // If the lowest bit is set, multiply the current base into the result
26        if (exponent & 1n) result = (result * base) % modulus;
27        // Shift exponent right by one bit
28        exponent >>= 1n;
29        // Square the base for the next bit position
30        base = (base * base) % modulus;
31    }
32    return result;
33}
34
35// Precompute factorials and their modular inverses.
36// 0! = 1 and its inverse is also 1.
37factorials[0] = 1n;
38inverseFactorials[0] = 1n;
39for (let i = 1; i < MAX_SIZE; i++) {
40    // i! = (i-1)! * i
41    factorials[i] = (factorials[i - 1] * BigInt(i)) % MOD;
42    // Modular inverse of i! using Fermat's Little Theorem:
43    // a^(MOD-2) ≡ a^(-1) (mod MOD) when MOD is prime
44    inverseFactorials[i] = qmi(factorials[i], MOD - 2n, MOD);
45}
46
47/**
48 * Computes the binomial coefficient C(n, k) mod MOD.
49 * Formula: C(n, k) = n! / (k! * (n-k)!)
50 * Using precomputed factorials and their inverses for O(1) lookup.
51 *
52 * @param n - Total number of items
53 * @param k - Number of items to choose
54 * @returns C(n, k) mod MOD
55 */
56function comb(n: number, k: number): bigint {
57    return (((factorials[n] * inverseFactorials[k]) % MOD) * inverseFactorials[n - k]) % MOD;
58}
59
60/**
61 * Counts the number of valid arrangements where exactly k people are visible
62 * given a person positioned at index `pos` in a line of `n` people.
63 *
64 * The line is split into a left segment (l people) and a right segment (r people).
65 * We distribute the k visible people across both sides, choosing `a` from the left
66 * and `b = k - a` from the right. The factor of 2 accounts for symmetry.
67 *
68 * @param n - Total number of people in the line
69 * @param pos - The position index of the reference person
70 * @param k - The exact number of visible people required
71 * @returns The total count of valid arrangements mod MOD (as a number)
72 */
73function countVisiblePeople(n: number, pos: number, k: number): number {
74    // Number of people to the left of the reference position
75    const l = pos;
76    // Number of people to the right of the reference position
77    const r = n - pos - 1;
78    let ans = 0n;
79
80    // Iterate over how many of the k visible people come from the left side
81    for (let a = 0; a <= Math.min(k, l); a++) {
82        // The remaining visible people must come from the right side
83        const b = k - a;
84        // Only valid if the right side has enough people
85        if (b <= r) {
86            // Multiply choices from both sides; factor of 2 for symmetry
87            ans = (ans + ((((2n * comb(l, a)) % MOD) * comb(r, b)) % MOD)) % MOD;
88        }
89    }
90
91    return Number(ans);
92}
93