# Hackerrank Solution: Sherlock and Permutations

Watson asks Sherlock: Given a string S of N 0's and M 1's, how many unique permutations of this string start with 1?

Help Sherlock by printing the answer modulo \((10^9+7)\).

## Input Format

First line contains T, the number of test cases. Each test case consists of N and M separated by a space.

## Output Format

For each test case, print the answer modulo \((10^9+7)\).

## Constraints

- \(1 \leq T \leq 200\)
- \(1 \leq N,M \leq 1000\)

## Solution

In total we have \(M+N\) bits in the string. Since the first bit has to be 1, we have \(M+N-1\) places, from which we choose exactly \(N\) zeros under the modular concurrence. So the solution to our problmem is

\[{M+N-1\choose N}\equiv \frac{(M+N-1)!}{N!(M-1)!} \pmod{10^9+7}\]

For Project Euler Problem 16 we implemented a highly optimized n over k algorithm with complexity \(O(k)\):

```
def noverk(n, k):
c = 1
k = min([k, n - k])
n = n - k
for i in range(1, k + 1)
c = c * (n + i) / i
return c
```

Converting this algorithm to an algorithm which operates under a modular concurrence should be easy, as the recursive nature of the algorithm can make use of the modular multiplication property

\[(a\cdot b)\bmod m = (a\bmod m \cdot b\bmod m)\bmod m\]

The only problem is the factor \(\frac{1}{i}\), which requires taking the modular inverse of \(i\). But since \(10^9+7\) is prime, we can make use of Eulers Theorem, which will make things much easier!

In general, Eulers Theorem states that if $\gcd(a, n) = 1$, then

\[a^{\varphi(n)} \equiv 1\pmod{n}\]

But since \(n\) is a prime number \(p=10^9+7\) in our case, we get

\[a^{p-1} \equiv 1\pmod{p}\]

Dividing both sides by \(a\) gives us a solution for the modular inverse under a prime number \(p\):

\[a^{p-2} \equiv a^{-1}\pmod{p}\]

When implementing the solution in Python, we can use the `pow()` function with its third argument for modular exponentiation to save an own implementation. All in all, the solution then looks like this

```
def noverkmodm(n, k, m):
c = 1
k = min([k, n - k])
n = n - k;
for i in range(1, k + 1):
c = (c * ((n + i) % m) * pow(i, m - 2, m)) % m;
return c
def solve(n, m):
return noverkmodm(n + m - 1, n, 10 ** 9 + 7)
```