My official editorial to this problem turned out to be very popular and liked by HackerEarth community, so I decided to post it here also
The original problem statement is available here.
This problem is pure math. Let's reformulate it a little bit first.
Let represents a single Arjit's soldier and represents a single soldier who belongs to Fatal Eagle. Then we are interested in the number of sequences of 's and 's consisting of 's and 's, such that in any prefix of these sequences the number of 's is not greater than the number of 's. We call any such sequence a valid sequence and any not valid sequence we call an invalid one.
Why I called elements of sequences and and not for example and ? Well, this helps us to represent the problem in a graphical way which is probably the greatest explanation here.
Let's consider a grid of size and any path starting in its upper left corner and ending in its bottom right corner. Any such path uses moves right and moves down. If we represent a right move as and a down move as , we can see an analogy to our sequences! Great, but we are searching for only valid sequences, how a valid sequence is represented on the grid? Well, it is any path which does not cross the diagonal. Consider the following illustration of a valid path:
It is easy to see, that any valid path does not cross the diagonal, so in its every prefix, it has at least as many 's as 's. Sounds great, but how to count the number of valid walks? We will do this counting the number of all paths and subtracting from it the number of invalid paths.
There are paths in the grid, because we have to make moves and from these moves has to be down moves.
The only remaining task is to count the number of invalid paths. Remember that any invalid path crosses diagonal at least once? Let be a point when it crosses it for the first time. Take a look at the illustration for better understanding:
Let's now do some clever transformation which is super useful in counting invalid paths. Let's take any invalid path and its point . Then reflect its subpath which begins at , the transformation is presented as follows:
Now notice that any invalid path can be transformed this way and the transformations of two different invalid paths produces two different paths on grid of size . Moreover, any path on can be produced from an invalid path on grid , so there is a bijection between invalid paths on grid and paths on grid. From these observations, we know that there are invalid paths.
Putting it together
The answer to this problem is and you can compute it using factorials after expanding the equation. In order to get the result modulo , you can use modular inverse to simulate division with multiplication.
If you expand the final equation, , and simplify it, you will get the definition of the Catalan Number, i.e . It arrises so many times in counting that you should be familiar with it definitely.