8595. Dogs and monkeys

Barish has n dogs and m monkeys. He wants to line them up. But he doesn’t want to put two dogs or two monkeys together, because in this case they start to fight. How many different arrangements exists, such that neither the monkeys nor the dogs fight. Print the answer modulo 10⁹ + 7. Keep in mind that dogs and monkeys are different.

Input. Two integers n and m (1 ≤ n, m ≤ 10⁵).

Output. Print the number of different ways to arrange monkeys and dogs modulo 10⁹ + 7.

Sample input 1	Sample output 1
2 2	8
Sample input 2	Sample output 2
3 2	12
Sample input 3	Sample output 3
1 8	0

SOLUTION

combinatorics

Algorithm analysis

If m > n + 1 or m < n – 1, then the required arrangement does not exist, the answer is 0. If m = n, then the dogs and monkeys should be arranged alternating with each other. For example, on even places you can put dogs (n! ways, since all dogs are different), on odd places – monkeys (m! ways, monkeys are different).

Similarly, you can put dogs on odd places, and monkeys on even places. Total for m = n we have 2 * n! * m! ways.

If the number of dogs is 1 more than monkeys (or, respectively, the number of monkeys is 1 more than dogs), then the number of ways of their location is n! * m!

Algorithm realization

Computations should be carried out modulo MOD = 10⁹ + 7.

#define MOD 1000000007

Function fact computes the factorial n!

long long fact(int n)

{

long long res = 1;

for (int i = 2; i <= n; i++)

res = (res * i) % MOD;

return res;

}

The main part of the program. Read the input data.

scanf("%d %d", &m, &n);

If the number of dogs is 2 more than monkeys or the number of monkeys is 2 more than dogs, then such an arrangement is impossible.

if (m > n + 1 || m < n - 1)

res = 0;

If the number of dogs and monkeys are the same.

else if (m == n)

res = (fact(n) * fact(n) * 2) % MOD;

else

If the number of dogs is 1 more than monkeys or the number of monkeys is 1 more than dogs.

res = (fact(n) * fact(m)) % MOD;

Print the answer.

printf("%lld\n", res);