For a real number \(t\), let time \(t\) denote the time \(t\) seconds after time \(0\).

For each non-negative integer \(t=0,1,\ldots, X\), let \(p[t]\) be the probability that songs switch at time \(t\).

In an event where song \(1\) is played at time \((X+0.5)\), the event where that song starts playing at times \(X, (X-1),\ldots, (X-T_1+1)\) are exclusive from each other, and exactly one of them is satisfied in such an event. Thus, it is sufficient to find the sum of the probability that song \(1\) starts playing at time \(t\) over \(t=X, (X-1),\ldots, (X-T_1+1)\). (Note that if song \(1\) is started on one of them, the song is always played at time \((X+0.5)\).) Since the songs are chosen at equal probability, the probability that song \(1\) starts playing at time \(t\) is (the probability that a song starts playing at time \(t\)\(\times\frac{1}{N}\)).

Thus, the answer is

\[ \frac{1}{N}(p[X-T_1+1]+p[X-T_1+2]+\cdots+p[X]), \]

if \(T_1\leq X+1\), and

\[ \frac{1}{N}(p[0]+p[X-T_1+2]+\cdots+p[X]) \]

if \(X\leq T_1\).

Therefore, it is sufficient to find each \(p[i]\), which can be found with a Dynamic Programming (DP). First of all, \(p[0]=1\). For \(t\geq 1\), one can consider which song ends at time \(t\), so that \(p[t]\) is found as the sum of “the probability that song \(k\) starts at time \((t-T_k)\)” over \(k=1,2,\ldots,N\). Just as we have already discussed, this is \(0\) if \(t-T_k<0\) and \(\frac{1}{N}p[t-T_k]\) if \(t-T_k\geq 0\). Therefore, by letting \(p[t]=0\) for \(t<0\) for convenience, it is sufficient to compute \(p[t]=\frac{1}{N}(p[t-T_1]+p[t-T_2]+\cdots+p[t-T_N])\).

Computing \(p[t]\) for each \(t\) costs \(O(N)\) time, for a total of \(O(NX)\) over all \(t=1,2,\ldots,X\); then, computing the answer costs \(O(\min(T_1,X))\). Hence, the overall complexity is \(O(NX)\), which is fast enough to solve the problem.

Sample code in C++:

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

using mint = modint998244353;

int main(void) {
	int n,x;
	mint ans;
	
	cin>>n>>x;
	vector<int>t(n);
	for(int i=0;i<n;i++)cin>>t[i];

	vector<mint>p(x+1);
	p[0]=1;
	if(t[0]>x)ans+=p[0]/((mint)n);
	for(int i=1;i<=x;i++){
		for(int j=0;j<n;j++)if(t[j]<=i)p[i]+=p[i-t[j]];
		p[i]/=((mint)n);
		if(i+t[0]>x)ans+=p[i]/((mint)n);
	}

	cout<<ans.val()<<endl;
	return 0;
}