We will solve the case the elements of \(A\) are distinct. (If \(A\) contains equal numbers, the same solution can be used after ordering equal numbers according to their indices.)

Below, a sequence where adjacent elements sum to at most \(K\) is said to be valid.

Consider obtaining a valid sequence \(B\) that is a permutation of \(A\), as follows.

• Start with an empty sequence \(B\). Perform the following operation \(N\) times to move all elements of \(A\) to \(B\).
  • Let \(L\) and \(R\) be the smallest and largest values in \(A\), respectively. Compare \(L+R\) and \(K\).
    1. If \(L+R \lt K\), remove \(L\) from \(A\) and put it in an arbitrary position in \(B\).
    2. If \(L+R \geq K\), remove \(R\) from \(A\) and put it in an arbitrary position in \(B\).
  • In either case, \(B\) must be valid after the insertion.

Consider the number of sequences \(B\) that can be generated in this way.
Let us begin with verifying the following fact:

• When inserting \(L, R\) in \(B\), we have \(L \lt K/2, R \geq K/2\).

This immediately holds from the condition in the branch. (For respective cases, we have \(2L \leq L+R \lt K\), \(2R \geq L+R \geq K\).)

Now, after performing the operation \(i\) times \((0 \leq i \lt N)\), the length of \(B\) is \(i\). Here, let us call a gap between \(B_j\) and \(B_{j+1}\) \((1 \leq j \leq i + 1)\) that satisfies the following condition a space. (Let \(B_{0}=B_{i+1}=\infty\) for convenience.)

• (current \(\min A\)) \(+ \min(B_{i-1},B_i) \geq K\)

Then, let \(S_i\) be the number of spaces in \(B\) after performing the \(i\)-th operation. (Particularly, if \(i=0\), \(B\) is empty and \(S_0 = 1\).)

Here, it can be proved that one always inserts an element of \(A\) into a space.

(Proof outline) When \(L\) is inserted, the proposition obviously holds from the definition of space. Consider the case \(R\) is inserted. Assume that the \(R\) inserted by the \(i\)-th operation can be represented as \(K/2 + d\) \((d \geq 0)\). Since \(L+R \geq K\), we have \(L \geq K/2 - d\), so if \(j\) does not correspond to a space, \(\min(B_{j}, B_{j+1})\) is smaller than \(K/2 + d\). Also, every element in \(B\) at this point is either less than \(K/2-d\) or at least \(K/2 + d\). Therefore, \(\min(B_{j}, B_{j+1}) \lt K/2-d\) holds for non-space positions, into which \(R\) cannot be inserted.

Additionally, the following facts can be shown.

• When the \(i\)-th operation inserts \(L\), the number of spaces decreases by \(1\).
• When the \(i\)-th operation inserts \(R\), the number of spaces increases by \(1\).

(Proof outline) The former is obvious from \(L \lt K/2\). The latter follows from the fact that when the \(R\) inserted by the \(i\)-th operation can be represented as \(K/2 + d\) \((d \geq 0)\), all elements in \(A\) less than \(K/2\) are at least \(K/2 - d\).

Moreover, the value inserted by the \(i\)-th operation is constant, no matter where it is inserted. Thus, it can be said that the sequence \(S_0, S_1, S_2, \dots, S_N\) is constant, no matter how one performs the operations.

From the arguments above, the number of sequences that can be generated by the above procedure is \(\prod_{i=0}^{N-1} S_i\).

Let \(C_i\) be the \(B\) at the end of the \(i\)-th operation. The whole process of \(N\) operations can be represented as a sequence of length \(N+1\): \((C_0, C_1, \dots, C_N)\). Below, we call such a sequence an operation array.
So far, we have explained how one obtains a sequence from an operation array. Actually, it can be proved that the set of all sequences generated by operation arrays covers all valid sequences that are permutations of \(A\).
To prove this, we will explain how one conversely obtains an operation array from a sequence. For a permutation \(B\) of \(A\) where adjacent elements sum to at most \(K\), consider performing the following operation \(N\) times to empty \(B\).

• Choose an element \(x\) in \(B\) that minimizes \(\vert K/2 - x \vert\) and remove it. (If there are multiple such elements, choose the one that itself is the smallest.)

Here, it can be shown that \(B\) is always valid during the process.

(Proof outline) Let \(d\geq 0\). When removing \(x=K/2-d\), both elements adjacent to \(x\) are at least \(K/2+d\), so \(B\) is still valid after removing \(x\). When removing \(x=K/2+d\), every elements remaining in \(B\) are either less than \(K/2-d\) or at least \(K/2 + d\). If \(x\) is adjacent to a number less than \(K/2-d\), one can inductively derive a contradiction, so \(x\) must be adjacent to numbers at least \(K/2 + d\), in which case \(B\) is still valid after removing \(x\).

Moreover, it can also be verified that the \(i\)-th element removed by the removing operation equals the \((N+1-i)\)-th element inserted by the inserting operation. (Proof is omitted.)

Let \(C_{N-i}\) be the \(B\) after \(i\) removing operations. The whole process of \(N\) removing operations can be represented as a sequence of length \(N+1\): \((C_N, C_{N-1}, \dots, C_1, C_0)\). From the above arguments, the reversal of this sequence \((C_0, C_1, \dots, C_N)\) is a valid operation array.

Therefore, we have constructed a bijection between the set of operation arrays and the set of sequences, so the answer to the problem is \(\prod_{i=0}^{N-1} S_i\). One can use sorting and std::map to compute it in about \(\mathrm{O}(N \log N)\) time, which is fast enough.

• Sample implementation (C++)

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

mint fac[200200] = {1}, ans = 1;
int N, K, A[200200], S = 1;
map<int, int> m;

int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> A[i], m[A[i]]++;
  for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i;
  sort(A, A + N);
  for (int i = 0, j = N - 1; i <= j;) {
    if (A[i] + A[j] < K) {
      ans *= S--, i++;
    } else {
      ans *= S++, j--;
    }
  }
  for (auto& [_, v] : m) ans /= fac[v];
  cout << ans.val() << "\n";
}