### PROBLEM LINK:

**Author**: Devendra Agarwal

**Tester**: Anudeep Nekkanti

**Editorialist**: Amit Pandey

### DIFFICULTY:

Simple.

### PREREQUISITES:

Dynamic programming and basic mathematics.

### PROBLEM:

You are given a function f which is defined as:

Find

### QUICK EXPLANATION:

Let r = \min(r,N-r). There will be three cases: x \le r, r < x \le N-r and

N-r < x \le N. Calculate power of x in each of the case and multiply them taking modulo M.

### EXPLANATION:

The give problem can be solved using simple dynamic programming approach.

Let r = \min(r,N-r) and call F(N,r) = \frac {f(N)}{f(r)f(N-r)} .

**Case 1**(x \le r):

Power of x in f(N)= N
-x+1.

Power of x in f(r)= r-x+1.

Power of x in f(N-r)= (N-r)-x+1.

Hence, Power of x(\le r) in F(N,r)= (N-x+1) - (r-x+1) - ((N-r)-x+1) = x-1.

**Case 2**(r < x \le N-r):

Power of x in f(N)= N-x+1.

Power of x in f(r)= 0. as (x > r)

Power of x in f(N-r)= (N-r)-x+1.

Hence, Power of x in F(N,r)= (N-x+1) - ((N-r)-x+1) = r .

**Case 3**(N-r < x \le N):

Power of x in f(N)= N-x+1.

There will not be any term corresponding to denominator.

Hence, Power of x in F(N,r)= (N-x+1).

As, there can be large number of queries. We need to do some pre-processing to give results.

As, results to first and third case doesn’t depend on the value of r, we can pre-process them and store.

```
//Case I : For the given value of r, fordp[r] will store multiplication
of all x corresponding to the first case.
for(int i=1;i<=N/2;i++)
fordp* = (fordp[i-1]*binpow(i,i-1,M))%M;
```

In case 2, it can be noticed that power of x depends on r and the distance of r and N-r from N/2 will be the same. So, we can store multiplication of terms which are equi-distance from center in an array. So, that we can get value of Midr = \prod_{r+1}^{N-r} x in constant time.

```
//Case 2 : You can get Midr in O(1) time.
if(N&1)
betdp[N/2] = N/2 +1;
else
betdp[N/2]=1;
for(ll i=N/2-1;i>=1;i--)
betdp* = ((ll)((betdp[i+1]*(i+1))%M)*(ll)(N-i))%M;
```

Case 3 will not depend on the value of r, so we can do it similar to case 1.

```
//Case III
for(ll i=1;i<=N/2;i++)
backdp*= (backdp[i-1]*binpow(N-i+1,i,M))%M;
```

Finally you can calculate the output easily. See Setter’s

```
(http://www.codechef.com/download/Solutions/COOK55/Setter/FOMBRO.cpp) for the detailed implementation.
Second case i.e. calculating $\prod_{r+1}^{N-r} x % M$ can also be done using the segment tree. In the segment tree, a node will store the multiplication of both of the children mod $M$. Refer this wonderful [tutorials](http://letuskode.blogspot.in/2013/01/segtrees.html) for the more details on segment tree. See [tester's code](http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp) for the implementation of this approach.
### Solutions:
Setter's solution can be found [here](http://www.codechef.com/download/Solutions/COOK55/Setter/FOMBRO.cpp).<br>
Tester's solution can be found [here](http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp).
```