### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

At first, let’s define some notations. Let f(**N, M, K**) be the answer of this problem. And let **g(N, M, K**) = **f(N, M, K) - f(N-1, M, K)** be the number of the valid answers if Ciel use just N menus. And let **h(N, M, K)** be the number of patterns of Ciel’s feeding if Ciel must use every first **N** menus at least once.

Then **h(N, M, K) = N! * g(N, M, K)**, because Ciel has **N!** patterns for each valid answer used just **N** menus. And if Ciel can use first **N** menus (but she doesn’t have to use every menus), the number of patterns of Ciel’s feeding is

**N * (N-1) * (N-2) * … * (N-K+1) * (N-K) ^{M-K} = N! / (N-K)! * (N-K)^{M-K}, if M ≤ K**

**N * (N-1) * (N-2) * … * (N-M+1) = N! / (N-M)!**, otherwise.

Therefore we can calculate **h(N, M, K)** as (the above) - **h(N-1, M, K) - h(N-2, M, K) - … - h(0, M, K)**. Then we can obtain **g(N, M, K) as h(N, M, K) / N!**, and **f(N, M, K)** as **g**(0, **M, K) + g(1, M, K) + … + g(N, M, K)**. If the factorials 0!, 1!, …, 200! and its inverses are precalculated and stored, then we can calculate the answer for each case with **O**(N^{2} log **M)** time.

Note that **x** / **y** is calculated as **x * y**^{P-2} in modulo **P**, where **P** is a prime. Because, let be **z = x / y** (not in modulo **P**) and z be an integer, then there is an unique integer **k** (0 ? **k < P)** such that **z = x * k** in modulo **P**, and **y * y**^{P-2} = **y**^{P-1} = 1 in modulo **P** by Fermat’s little theorem. Therefore **k** should be **y**^{P-2}, since **x = z * y = x * k * y** in modulo **P**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.