1885: Red And Blue

Hedy has n red unique beads and m blue unique beads in his hand now. But it’s time for coding so that he has to let down all the beads. He has a circular plate and he will put all the beads into it. However, he just doesn’t want to put them into it with an arbitrary order. Instead, he wants to arrange them in such order that no blue beads are neighbors to each other. And he wonders that how many different ways he could arrange all beads in to the circular plate. Could you please help him to solve the problem?

There are multiple cases. Each case contains two numbers n and m. n is the number of red beads and m is the number of blue beads. 3 <= n,m <= 10^14

Calculate the ways of different arrange. Since the answer would be very large, you just need to output the answer mod 10000019. If it is impossible to arrange the beads, output -1.

3 3
5 3

12
1440