This problem is an exercise of inverse of polynomial. There are many problems that can be boiled down to computing inverses of polynomials and formal power series, so we recommend you learning from this problem if you want to become an expert of combinatorics.

First, let us define \(f(t)\) as follows. The sought answer is \(f(T)\).

• \(f(t)\) \(:=\) (the probability that three people are at \(A\), \(B\), and \(C\) at time \(0\) and they gather at the same point at time \(t\) for the first time).

The condition “for the first time” bothers, so let us first count without caring it, and then compute \(f(t)\).
Let \(g(t)\) and \(h(t)\) be defined as follows:

• \(g(t)\) \(:=\) (the probability that three people are at \(A\), \(B\), and \(C\) at time \(0\) and they gather at the same point at time \(t\)).

• \(h(t)\) \(:=\) (the probability that three people are at \(0\), \(0\), and \(0\) at time \(0\) and they gather at the same point at time \(t\)).

Suppose that we have obtained \(g(t)\) and \(h(t)\) \((0 \leq t \leq T)\). Then \(f(T)\) can be computed in a total of \(\mathrm{O}(T^2)\) time using the following relation between \(f(t)\), \(g(t)\), and \(h(t)\) (this is a kind of DP (Dynamic Programming) so-called “exclusion principle”):

\[f(t) = g(t) - \sum_{0 \leq u \lt t} f(u) h(t - u).\]

How can we optimize this DP? First, the left hand side in the equation above is a convolution with respect to \(f\), so we can apply divide-and-conquer FFT (Fast Fourier Transform) in a total of \(\mathrm{O}(T \log^2 T)\), as also described in the editorial of ABC 212 H. This is already fast enough to get accepted, but using generating functions makes it even faster.
The ordinary generating functions \(F\), \(G\), and \(H\) of \(f\), \(g\), and \(h\), respectively, are

\[F(x) = \sum_{i=0}^\infty f(i) x^i, G(x) = \sum_{i=0}^\infty g(i) x^i, H(x) = \sum_{i=0}^\infty h(i) x^i.\]

How can we represent \(F\) with \(G\) and \(H\)? Using the recurrence relation above,

\[ \begin{aligned} &\sum_{t=0}^\infty f(t) x^t = \sum_{t=0}^\infty \left( g(t) - \sum_{0 \leq u \lt t} f(u) h(t - u) \right) x^t \\ &\to F(x) = G(x) - F(x) (H(x) - h(0)), \end{aligned} \]

then we use \(h(0) = 1\) to obtain

\[ \begin{aligned} &\to F(x) = G(x) - F(x) (H(x) - 1) \\ &\to F(x) H(x) = G(x) \\ &\to F(x) = \frac{G(x)}{H(x)}. \end{aligned} \]

Thus, once we compute up to \(T\)-th order of the multiplicative inverse \(\frac{1}{H(x)}\) of \(H(x)\), we can also obtain the \(T\)-th coefficient of \(F(x)\). The inverse of a formal power series can be computed in an \(\mathrm{O}(T \log T)\), as also described in the editorial of ABC260 Ex.

By the observation above, we now know that all we need is \(g\) and \(h\) to obtain \(f(T)\) in an \(\mathrm{O}(T \log T)\) time. In order to find \(g\) and \(h\), let us solve the following problem.

The three guys are at \(X\), \(Y\), and \(Z\) at time \(0\). Let \(p(t)\) be the probability that they are at the same point at time \(t\). Enumerate \(p(0), p(1), \dots, p(T)\).

(Hereinafter we define \(\frac{1}{K!} = 0\) and \(\binom{N}{K} = 0\) if \(K\) is negative or non-integer.)

Let \(p(t, w)\) be the probability that the three guys gather at point \(w\) at time \(t\). Then we have

\[p(t, w) = \frac{1}{2^{3t}} \binom{t}{\frac{t + w - X}{2}} \binom{t}{\frac{t + w - Y}{2}} \binom{t}{\frac{t + w - Z}{2}}.\]

Using

\[q(i) = \frac{1}{\left(\frac{i-X}{2}\right)! \left(\frac{i-Y}{2}\right)!\left(\frac{i-Z}{2}\right)!},\]

\[r(i) = \frac{1}{\left(\frac{i+X}{2}\right)! \left(\frac{i+Y}{2}\right)!\left(\frac{i+Z}{2}\right)!},\]

we have

\[p(t, w) = \frac{(t!)^3}{2^{3t}} q(t + w) r(t - w)\]

so, by replacing with \(t + w = u\), we get

\[p(t) = \sum_w p(t, w) = \frac{(t!)^3}{2^{3t}} \sum_u q(u) r(2t - u).\]

Therefore, \(p(t)\) for \(0 \leq t \leq T\) can be enumerated by precomputing the binomial coefficients, generate the sequences of \(q\) and \(r\), extract the \(2t\)-th \((0 \leq t \leq T)\) element of the convolution of \(q\) and \(r\), and multiplying it by \(\frac{(t!)^3}{2^{3t}}\). (Note that appropriate offset is needed for convolution because \(u\) and \(2t - u\) may be a negative index.)

Therefore, the problem can be solved in a total of \(\mathrm{O}((A+B+C+T) \log (A+B+C+T))\) or \(\mathrm{O}(T \log T + A + B + C)\) time, which is fast enough. (You may even spend \(\mathrm{O}(T \log^2 T)\) time for finding an inverse, and your code will still be accepted.)

Bonus: how can we generalize it to \(N\) \((N \leq 10^5)\) people instead of three?