What about 10^5 queries?

My solution is Log(b — a) * (b — a) * Log(w). I iterate from a to b foreach i finding how many words would be on each next string of length i. This is O((b — a) / i * f(i)), where f(i) is the complexity of "finding how many words would be on each next string of length i".

f(i) can be doen with binsearch: lets assume we've already proceded L words, so now we have to find maximum of such R that lengths of words from [L + 1, R] + R — L(count space characters) is <= i. Well, calculate prefix sums for words' length, then find R simply with binsearch. Dont forget to add length of L + 1 word to your answer(thats what we have to do :) )

Why is this (b — a) * Log(b — a) * log(w)? Log(w) goes for binsearch obviously; for some reason Sum(i / n, {i from 1 to n}) is Log(n) / n, so when we iterate for each i in [a, b] we do O(b — a) * Log(b — a) operations. Idk why it passes time limit, it looks like ~1.8 * 10^8, but it does. That's it

Or u could just copy it from input

It's not a bug, it's a feature =)

Here's our code (author is meshanya). It passed with 2x gap, even though it is Java. Actual solution is in method solve() (as it is always the case with CHelper's code).

There is one solution that passes the tests but is wrong:

find k = c / (a+b-1)

let G(i, j) = F(i, j) + k

now G(i, j) = aG(i, j-1) + bG(i-1,j)

find G(n, n) and use F(n, n) = G(n, n) — k to obtain final solution.

solution fails on case where a+b-1 = 0 (mod 10^6+3)

There are also solutions that work ;). To recollect, main problem is to compute sum . Let S(k) be sum of all summands such that i + j = k. We can note that it is almost true that S(k) = (a + b)S(k - 1). It is true for k ≤ n - 2, however for k > n - 2 you need to subtract two terms, which can be done in constant time (possibly after some precomputations of factorials etc.). Key argument here is of course

Если серьёзные проблемы с точностью, а времени хватает, то можно представить , , найти f_b·g_b, f_b·g_s, f_s·g_b, f_s·g_s с помощью вещественного FFT, а потом посчитать . Там коэффициенты уже порядка p получаются во всех четырёх слагаемых.

Ещё можно считать по двум другим хорошим модулям с произведением больше 10^12, чтобы однозначно восстановить ответ по модулю p.

Но у меня и так в long double зашло.