If we can do all operations and all $$$a_i$$$ remain non-negative, then the sum of $$$a_i$$$ is at least the sum of $$$b_j$$$ ($$$\sum a \ge \sum b$$$). Since we consider $$$k$$$ operations, each $$$a_i$$$ cannot contribute more than $$$k$$$ times, we can replace it by $$$\min(a_i, k)$$$. And then we check that the sum is still at least the sum of $$$b$$$. The assumption that $$$b$$$ is non-increasing is here because we want to verify the condition only for the maximal set of $$$k$$$ operations. If we can do $$$k$$$ maximal operations then we can do every other set of $$$k$$$ operations.

To show that, I want to prove that swapping two adjacent operations $$$k_1$$$ and $$$k_2$$$ is possible. if $$$k_1 = k_2$$$, it's trivial. Then, without loss of generality, $$$k_1 \gt k_2$$$.

Assume the array $$$a$$$ is sorted. The operations will decrease such positions that the array remains sorted. In order to do that, we pick positions from greater values left to right. For example, the red $$$8$$$ positions in this array would be picked.

$$$[1, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 7, 8, 8]$$$

$$$[1, 2, 3, 3, \color{red}{4}, \color{red}{4}, 4, 4, 4, 4, \color{red}{5}, \color{red}{5}, \color{red}{6}, \color{red}{7}, \color{red}{8}, \color{red}{8}]$$$

Notice that an operation decreases some suffix and some prefix of the next value. Also, this is the only way to remain the array sorted.

We show that the multiset of indices selected by the $$$k_1$$$ and $$$k_2$$$ operations is the same regardless of whether $$$k_1$$$ is applied before $$$k_2$$$ or $$$k_2$$$ before $$$k_1$$$. Since there is no ambiguity in the choice of positions, we can actually only look at the number of positions with a certain value that were decreased zero, once or twice.

Denote $$$c_x$$$ as the frequency of $$$x$$$ in the array $$$a$$$.

Let's start with a simple case where the first operations only decreases the maximum value $$$x$$$. If $$$k_1 + k_2 \le c_x$$$, then the first $$$k_1 + k_2$$$ positions where $$$x$$$ is will be decreased. if $$$k_1 + k_2 \ge c_x$$$, then:

• If we apply $$$k_1$$$ first and then $$$k_2$$$, the first operation decreases $$$k_1$$$ entries equal to $$$x$$$. The second operation decreases the remaining $$$c_x - k_1$$$ entries equal to $$$x$$$, and then decreases entries equal to $$$x-1$$$ (some of which may have been equal to $$$x$$$ before applying $$$k_1$$$). Crucially, after applying $$$k_1$$$ there are at least $$$k_1$$$ occurrences of $$$x-1$$$, so the $$$k_2$$$ operation only affects values equal to $$$x$$$ or $$$x-1$$$. Consequently, all entries equal to $$$x$$$ become $$$x-1$$$, and exactly $$$k_2 - (c_x - k_1) = k_1 + k_2 - c_x$$$ entries equal to $$$x-1$$$ are further decreased.

• If we apply $$$k_2$$$ first and then $$$k_1$$$, the first operation decreases $$$k_2$$$ entries equal to $$$x$$$. The second operation decreases the remaining $$$c_x - k_2$$$ entries equal to $$$x$$$, and then decreases $$$k_1 + k_2 - c_x \le k_2$$$ entries equal to $$$x-1$$$. The inequality ensures that no other values are affected. Again, all entries equal to $$$x$$$ become $$$x-1$$$, and exactly $$$k_1 + k_2 - c_x$$$ entries equal to $$$x-1$$$ are decreased.

Now consider the more general case where $$$x$$$ is the maximum number such that $$$c_x + c_{x+1} + \ldots \gt k_1$$$. If no such $$$x$$$ exists, then $$$k_1 = n$$$, which means that all numbers are decreased by $$$1$$$ and the order of indices which we choose for $$$k_2$$$ won't change, so the swap of operations doesn't affect the resulting array.

Otherwise the first operation $$$k_1$$$ would look like this:

Red stripes show the positions that are decreased. We can split the array $$$a$$$ in four parts: $$$ \lt x$$$, $$$x$$$, $$$x+1$$$, $$$ \gt x+1$$$ (some of them, but not $$$x$$$, might be empty). Denote the number of decreased $$$x$$$-s as $$$L$$$ and the number of elements in the fourth part as $$$R$$$. As was mentioned before, the operation decreases some suffix and some prefix of entries of the number before it.

Assume $$$k_2 \le R$$$. Let's look at the sets of positions which $$$k_2$$$ would decrease if it's the first and if it's the second operation. They are the same, since the order, in which we pick indices, of the $$$R$$$ positions doesn't change after applying $$$k_1$$$ first, as it decreases all values in that suffix and all entries of the value before. On the other hand the sets of positions which $$$k_1$$$ would decrease are also the same. In both cases the number of elements that are greater than $$$x$$$ is the same and less than $$$k_1$$$, so all of them will be decreased. The remaining prefix is unaffected by $$$k_2$$$, so the order of positions chosen in the prefix is also the same.

Now let's look at another case, where $$$k_2 \gt R$$$. I claim that the last $$$R$$$ elements will be decreased twice, hence can be ignored.

• first $$$k_1$$$ then $$$k_2$$$ — $$$k_1$$$ doesn't change the order of the first $$$R$$$ indices which are then chosen by $$$k_2$$$.

• first $$$k_2$$$ then $$$k_1$$$ — $$$k_2$$$ doesn't change the number of elements that are greater than $$$x$$$, so $$$k_1$$$ will decrease all of them, including all positions in $$$R$$$.

Now the problem reduces to $$$k_1$$$ decreasing only two distinct values. Once again, there are two cases.

1. $$$k_2 \le c_{x+1}$$$. Then let's look at the amount of entries of each value that will be decreased.

• first $$$k_1$$$ then $$$k_2$$$ — $$$k_1$$$ will decrease $$$c_{x+1}$$$ entries of $$$x+1$$$ and $$$k_1 - c_{x+1}$$$ entries of $$$x$$$. $$$k_2$$$ will then decrease $$$k_2$$$ entries of $$$x$$$, since $$$c_{x+1} \ge k_2$$$.

• first $$$k_2$$$ then $$$k_1$$$ — $$$k_2$$$ will decrease $$$k_2$$$ entries of $$$x+1$$$. $$$k_1$$$ will decrease $$$c_{x+1} - k_2$$$ entries of $$$x+1$$$ and $$$k_1 + k_2 - c_{x+1} \lt c_x + k_2$$$ entries of $$$x$$$. The inequality shows that $$$k_1$$$ will only decrease entries of $$$x$$$ and $$$x+1$$$.

1. $$$k_2 \gt c_{x+1}$$$. This case is tedious as there are subcases with $$$x - 1$$$, but the logic is the same, so I leave it as an exercise to the reader :)

Therefore, in all cases both orders of operations result in the same array, so we can swap adjacent operations without any effect. And if we can swap adjacent operations, we can get any permutation of operations we want.

Consider a function $$$f(k) = \sum \limits_{i=1}^n \min(k, a_i) - kt$$$. We want to find its minimum to check if it's less than $$$0$$$.

$$$f(k + 1) - f(k) = \sum \limits_{i=1}^n \min(k + 1, a_i) - \min(k, a_i) - t$$$. The sum of the differences of the minima is the number of $$$a_i \gt k$$$, which decreases with $$$k$$$, so $$$f$$$ is a concave function. That means that the minimum value is either $$$f(0)$$$ or $$$f(m)$$$. Since $$$f(0) = 0$$$ we only need to check $$$f(m)$$$.

For each window of size $$$k$$$ we choose $$$k$$$ different colors and decrease their frequency by $$$1$$$. That's exactly the process of the Theorem. The last window will have size $$$n \mod k$$$, there we put all the remaining colors. So we have operations $$$b_1 = b_2 = \ldots = b_{\lfloor \frac{n}{k} \rfloor} = k, b_{\lfloor \frac{n}{k} \rfloor} + 1 = n \mod k$$$. From the previous fact there are only two conditions we need to check, for the first $$$\lfloor \frac{n}{k} \rfloor$$$ operations and for all of them.

1. $$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor, a_i) \ge n - n \mod k$$$

2. $$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor + 1, a_i) \ge n$$$

The first condition means that there are at most $$$n \mod k$$$ values in $$$a$$$ that are greater than $$$\lfloor \frac{n}{k} \rfloor$$$.

The second condition together with the fact that $$$\sum a = n$$$ means that $$$\max(a) \le \lfloor \frac{n}{k} \rfloor + 1$$$.

Lastly, how do we select the colors for each cell? For the first window we just pick $$$n \mod k$$$ most frequent colors and then for each window of size $$$k$$$ we first pick colors and then from left to right select any color that can be put. It works because of pigeonhole principle (there are more allowed colors we can put than the number of banned colors).

We have

$$$\sum \limits_{i=1}^m min(k, b_i) \ge \sum \limits_{i=1}^k a_i$$$.

Since all $$$b_i = t$$$, this becomes

$$$m \cdot min(k, t) \ge \sum \limits_{i=1}^k a_i$$$.

For $$$k \le t$$$, this gives $$$km \ge \sum \limits_{i=1}^k a_i$$$. In particular, for $$$k = 1$$$ we obtain $$$m \ge a_1$$$, and since $$$a_1 \ge a_i$$$, this inequality also implies $$$km \ge ka_1 \ge \sum \limits_{i=1}^k a_i$$$ for every $$$k \le t$$$.

For $$$k \gt t$$$ the left-hand side is always $$$tm$$$, while the right-hand side increases till $$$\sum a$$$. Hence it suffices to check only $$$k = 1$$$ and $$$k = n$$$ to find minimal $$$m$$$.

1. $$$k = 1$$$. $$$m \ge a_1$$$

2. $$$k = n$$$. $$$tm \ge \sum a \Rightarrow m \ge \lceil \frac{\sum a}{t} \rceil$$$

Therefore $$$m = \max(a_1, \lceil \frac{\sum a}{t} \rceil)$$$.

1. The greedy algorithm to always decrease maximums produces the lexicographically largest possible sorted array among all arrays which are achievable with the operations.

using ll = long long;
using pii = pair<int, int>;

vector<pii> g[N];
ll dist[N];

void dfsUp(int v, int pr = -1) {
    for (auto &[u, w] : g[v])
        if (u != pr) {
            dfsUp(u, v);
            dist[v] = min(dist[v], dist[u] + w);
        }
}

void dfsDown(int v, int pr = -1) {
    for (auto &[u, w] : g[v])
        if (u != pr) {
            dist[u] = min(dist[u], dist[v] + w);
            dfsDown(u, v);
        }
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) x.begin(), x.end()

const int N = 1e5 + 10;
const int B = 320; // roughly sqrt N
int a[N];
int cnt[N];
ll sum = 0;

void add(int v) {
    sum += cnt[v];
    cnt[v]++;
}

void del(int v) {
    cnt[v]--;
    sum -= cnt[v];
}

int L = 0, R = -1; // the pointers

void move(int l, int r) { // move pointers to the query point
    while (R < r) {
        ++R;
        add(a[R]);
    }
    while (R > r) {
        del(a[R]);
        R--;
    }
    while (L > l) {
        L--;
        add(a[L]);
    }
    while (L < l) {
        del(a[L]);
        L++;
    }
}

struct query {
    int l, r, i;
};

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    int queries;
    cin >> queries;
    vector<query> q(queries);
    vector<ll> ans(queries);
    for (int i = 0; i < queries; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        q[i] = {l, r, i};
    }
    sort(all(q), [&](const query &a, const query &b) {
        int al = a.l / B;
        int bl = b.l / B;
        if (al != bl)
            return al < bl;
        return a.r < b.r;
    });
    for (auto &[l, r, i] : q) {
        move(l, r);
        ans[i] = sum;
    }
    for (int i = 0; i < queries; i++)
        cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

The movement of the $$$L$$$ and $$$R$$$ pointers can be viewed as traversing a Manhattan grid of size $$$n \times n$$$, where the X-axis corresponds to the $$$L$$$ coordinate and the Y-axis to $$$R$$$. In this context, queries are simply points on this plane that we traverse in some order. We partition the plane into $$$B \times B$$$ squares. The lower bound on the runtime $$$O(n \sqrt n)$$$ is achieved if we place a query in the bottom-left corner of each square — there would be exactly $$$\sqrt n \times \sqrt n = n$$$ queries. The upper bound is achieved with the following traversal:

We traverse the squares left to right, top to bottom. The $$$R$$$ pointer moves from $$$1$$$ to $$$n$$$ exactly $$$\frac{n}{B}$$$ times, while the $$$L$$$ pointer moves within each square by at most $$$B$$$ for each query. Thus, both pointers move $$$O(n \sqrt n)$$$ times, which determines the runtime.

Let's prove why it's always better to add to the smallest number, let $$$a \le b \le c$$$, then compare the three expressions: $$$(a+1)\times b \times c$$$, $$$a \times (b+1) \times c$$$, and $$$a \times b \times (c+1)$$$. Remove the common part $$$a \times b \times c$$$, and we get: $$$b \times c$$$, $$$a \times c$$$, $$$a \times b$$$.

$$$b \times c \ge a \times c$$$, since $$$a \le b$$$, similarly, $$$b \times c \ge a \times b$$$, since $$$a \le c$$$. Therefore, we can simply find the minimum $$$5$$$ times and add one to it. And thus, obtain the answer.

Another, primitive approach is to simply iterate through what we will add to $$$a$$$, $$$b$$$, and $$$c$$$ with three loops.

Since we can only add $$$5$$$ times, the time complexity of the solution is $$$O(1)$$$.

for _ in range(int(input())):
    arr = sorted(list(map(int,input().split())))
    for i in range(5):
        arr[0]+=1
        arr.sort()
    print(arr[0] * arr[1] * arr[2])

Let's say we want to connect two casseroles with lengths $$$x$$$ and $$$y$$$. We can disassemble one of them into pieces of length $$$1$$$ and then attach them to the casserole of size $$$y$$$. In total, we will perform $$$2x - 1$$$ operations. Since we want to connect $$$k$$$ pieces, at least $$$k - 1$$$ of them will have to be disassembled and then attached to something. If we attach something to a piece, there is no point in disassembling it, because to disassemble it, we will need to remove these pieces as well. Therefore, we want to choose a piece to which we will attach all the others. It will be optimal to choose a piece with the maximum size and attach everything to it. Thus, the answer is $$$2 \cdot (n - mx) - k + 1$$$, where $$$mx$$$ $$$-$$$ the length of the maximum piece.

Solution complexity: $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int T;
    cin >> T;
    while (T--){
        int n, k;
        cin >> n >> k;
        vector<int> s(k);
        int m = -1;
        for (int i = 0; i < k; i++){
            cin >> s[i];
            m = max(m, s[i]);
        }
        cout << 2 * (n - m) - k + 1 << '\n';
    }
}

for _ in range(int(input())):
    n,k = map(int,input().split())
    mx = max(map(int, input().split()))
    print((n - mx) * 2 - (k - 1))

Let $$$p$$$ be some permutation. Let's look at the contribution of the number $$$p_i$$$ to the sum $$$\sum_{i=1}^n {f(i)}$$$. If it is less than $$$k$$$, the contribution is $$$0$$$, otherwise the contribution is $$$p_i \cdot (n - i + 1)$$$. Similarly, let's look at the contribution of $$$p_i$$$ to the sum $$$\sum_{i=1}^n {g(i)}$$$. If it is greater than $$$m$$$, the contribution is $$$0$$$, otherwise it is $$$p_i \cdot (n - i + 1)$$$. Since $$$m \lt k$$$, each number gives a contribution greater than $$$0$$$ in at most one sum. Therefore, it is advantageous to place numbers not less than $$$k$$$ at the beginning, and numbers not greater than $$$m$$$ at the end. Also, numbers not less than $$$k$$$ should be in descending order to maximize the sum of $$$f(i)$$$. Similarly, numbers not greater than $$$m$$$ should be in ascending order to minimize the sum of $$$g(i)$$$.

For example, you can construct such a permutation: $$$n, n - 1, \ldots, k, m + 1, m + 2, \ldots, k - 1, 1, 2, \ldots, m$$$. It is easy to see that $$$\sum_{i=1}^n f(i)$$$ cannot be greater for any other permutation, and $$$\sum_{i=1}^n g(i)$$$ cannot be less for any other permutation, so our answer is optimal.

Solution complexity: $$$O(n)$$$.

for _ in range(int(input()):
    n,m,k = map(int,input().split())
    print(*range(n,m,-1), *range(1,m))

In this problem, there are two main solutions: dynamic programming and greedy algorithm.

Dynamic programming solution: $$$dp_i$$$ $$$-$$$ the minimum number of meters that need to be swum to reach the $$$i$$$-th cell. The base case of the dynamic programming is $$$dp_0 = 0$$$. Then, the update rule is: \begin{equation*} dp_i = \text{minimum of} \begin{cases} dp_{i-1} + 1& \text{if } A_i = \text{'W'} \\ min(dp_j) & \text{for all } j, \text{where:} \max(0, i — m) \le j < i \text{ and } A_j = \text{'L'} \end{cases} \end{equation*} Solution complexity: $$$O(nm)$$$.

Greedy algorithm solution: If we can jump, we want to jump to the shore if possible. If we can't, we want to jump to any log ahead to jump from it later. If we can't, we jump as far as possible to avoid crocodiles and swim as little as possible.

Solution complexity: $$$O(n)$$$.

def run() -> None:
    n,m,k = map(int, input().split())
    A = input()
    logs = [i for i in range(n) if A[i] == "L"]
    logs.append(n+1)
    i = -1
    next_log = 0
    while i < n-1:
        if m >= logs[next_log] - i:
            i = logs[next_log]
        else:
            i+=m
            if i > n-1:
                print("YES")
                return
            while i < n and i < logs[next_log]:
                if A[i] != "C" and k > 0:
                    i+=1
                    k-=1
                else:
                    print("NO")
                    return
        next_log +=1
    print("YES")
 
for _ in range(int(input())):
    run()

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k; 
        cin >> n >> m >> k;
        string s;
        cin >> s;
        vector<int> dp(n + 2, -1);
        dp[0] = k;
        for (int i = 1; i <= n + 1; i++) {
            if (i != n + 1 && s[i - 1] == 'C') 
                continue;
            for (int t = 1; t <= m; t++)
                if (i - t >= 0 && (i - t == 0 || s[i - t - 1] == 'L'))
                    dp[i] = max(dp[i], dp[i - t]);
            if (i > 1 && s[i - 2] == 'W') 
                dp[i] = max(dp[i], dp[i - 1] - 1);
        }
        if (dp[n + 1] >= 0) 
            cout << "YES\n";
        else 
            cout << "NO\n";
    }
}

Notice that $$$n * a - b$$$ is strictly less than $$$10^6$$$, i.e., it has no more than $$$6$$$ digits. The number of characters in the strange calculation $$$n * a - b$$$ is equal to $$$|n| * a - b$$$, where $$$|n|$$$ is the number of digits in n. Let's iterate over the value of $$$a$$$, and then determine the boundaries $$$minB$$$ and $$$maxB$$$ for it, such that $$$|n| * a \gt maxB$$$ and $$$|n| * a - minB \le 6$$$. Then: \begin{cases} minB = |n| * a- 6 \\ maxB = |n| * a- 1 \end{cases} Let's iterate over all $$$b$$$ from $$$minB$$$ to $$$maxB$$$. To quickly check the strange calculation, let's only find its first $$$|n| * a - b$$$ digits. This way, we can find all suitable pairs $$$(a, b)$$$.

Solution complexity: $$$O(a)$$$.

for _ in range(int(input())):
    n = int(input())
    sn = str(n)
    lenN = len(str(n))
    ans = []
    for a in range(1, 10001):
        minB = max(1, lenN * a - 5)
        maxB = lenN * a
        for b in range(minB, maxB):
            x = n * a - b
            y = 0
            for i in range(lenN * a - b):
                y = y * 10 + int(sn[i % lenN])
            if x == y:
                ans.append((a, b))
    print(len(ans))
    for p in ans:
        print(*p)

Let's consider the greedy algorithm ``take as long as you can''. Let's prove that it works. In any optimal division, if we take the first segment of non-maximum length, we will not violate the criteria if we transfer one element from the second segment to the first. Therefore, the given greedy algorithm is correct.

Now let's figure out how to quickly understand if the segment can be extended. First, find all divisors of the number $$$x$$$. If the number $$$a_i$$$ is not a divisor of it, then it cannot be included in any set of numbers whose product is equal to $$$x$$$, so we can simply add it to the segment. If $$$a_i$$$ is a divisor, we need to somehow learn to understand whether it, in combination with some other divisors, gives the number $$$x$$$ on the segment. We will maintain a set of divisors that are products of some numbers in the segment. To update the set when adding $$$a_i$$$, we will go through all the divisors of this set and for each divisor $$$d$$$ add $$$d \cdot a_i$$$ to the set. If we added the number $$$x$$$ to the set, $$$a_i$$$ will already be in the next segment and we need to clear the set.

P. S.: About implementation details and runtime. If you maintain the set in a set structure, then we get a runtime of $$$O(n \cdot d(x) \cdot \log(d(x)))$$$, where $$$d(x)$$$ is the number of divisors of $$$x$$$. Instead of a set, you can use, for example, a global array $$$used$$$ of size $$$10^5 + 1$$$, as well as maintain a vector of reachable divisors. Using these structures, you can achieve a runtime of $$$O(n \cdot d(x))$$$.

#include <iostream>
#include <vector>

using namespace std;

const int A = 1e6 + 1;
bool used[A];
bool divs[A];

void solve() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	vector<int> vecDivs;
	for (int d = 1; d * d <= x; d++) {
		if (x % d == 0) {
			divs[d] = true;
			vecDivs.push_back(d);
			if (d * d < x) {
			    vecDivs.push_back(x / d);
				divs[x / d] = true;
			}
		}
	}
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int ans = 1;
	used[1] = true;
	vector<int> cur{ 1 };
	for (int i = 0; i < n; i++) {
		if (!divs[a[i]])
			continue;
		vector<int> ncur;
		bool ok = true;
		for (int d : cur)
			if (1ll * d * a[i] <= x && divs[d * a[i]] && !used[d * a[i]]) {
				ncur.push_back(d * a[i]);
				used[d * a[i]] = true;
				if (d * a[i] == x)
					ok = false;
			}
		for (int d : ncur)
			cur.push_back(d);
		if (!ok) {
			ans++;
			for (int d : cur)
				used[d] = false;
			used[1] = true;
			used[a[i]] = true;
			cur = vector<int>{ 1, a[i] };
		}
	}
	for (int d : vecDivs) {
	    divs[d] = false;
	    used[d] = false;
	}
	cout << ans << '\n';
}

signed main() {
    int T;
    cin >> T;
    while (T--)
	    solve();
	return 0;
}

We will iterate over the size of the set $$$k$$$ and its $$$\text{MEOW}$$$, $$$m$$$. If $$$2k \geqslant n$$$, then the set $$$x$$$ will fill all the remaining numbers up to $$$n$$$, and there may still be some larger than $$$n$$$ in it, so the $$$MEOW$$$ of all such sets will be $$$2k+1$$$, and there will be a total of $$$C(n, k)$$$ such sets for each $$$k$$$. If $$$2k \lt n$$$, $$$m$$$ lies in the interval from $$$k+1$$$ to $$$2k+1$$$. Notice that there can be exactly $$$m - 1 - k$$$ numbers before $$$m$$$, and correspondingly $$$2k + 1 - m$$$ numbers to the right of $$$m$$$, so the answer needs to be added with $$$C_{m - 1}^{m - 1 - k} \cdot C_{n - m}^{2k + 1 - m} \cdot m$$$.

Asymptotic complexity of the solution: $$$O(n^2)$$$.

#include <iostream>

using namespace std;

const int mod = 1e9 + 7;

int add(int a, int b) {
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

int sub(int a, int b) {
    if (a < b)
        return a + mod - b;
    return a - b;
}

int mul(int a, int b) {
    return (int)((1ll * a * b) % mod);
}

int binpow(int a, int pw) {
    int b = 1;
    while (pw) {
        if (pw & 1)
            b = mul(b, a);
        a = mul(a, a);
        pw >>= 1;
    }
    return b;
}

int inv(int a) {
    return binpow(a, mod - 2);
}

const int N = 15000;
int f[N], r[N];

void precalc() {
    f[0] = 1;
    for (int i = 1; i < N; i++)
        f[i] = mul(f[i - 1], i);
    r[N - 1] = inv(f[N - 1]);
    for (int i = N - 2; i > -1; i--)
        r[i] = mul(r[i + 1], i + 1);
}

int C(int n, int k) {
    if (n < 0 || k < 0 || n < k)
        return 0;
    return mul(f[n], mul(r[k], r[n - k]));
}

inline void solve() {
    int n;
    cin >> n;
    int ans = 1;
    for (int k = 1; k <= n; k++) {
        if (2 * k >= n) {
            ans = add(ans, mul(2 * k + 1, C(n, k)));
            continue;
        }
        for (int m = k + 1; m <= 2 * k + 1; m++) {
            int c = mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m));
            ans = add(ans, mul(mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m)), m));
        }
    }
    cout << ans << '\n';
}

signed main() {
    int T = 1;
    cin >> T;
    precalc();
    while(T--)
        solve();
    return 0;
}