### coderdhanraj's blog

By coderdhanraj, 21 month(s) ago,

Hey Everyone,

I am stuck on the following problem. Need help!

### Problem: Unique Paths (Hard Version)

You are given a grid consisting of $n$ rows and $m$ columns. There are two types of cells good and bad. You can't move in a bad cell. There are $k$ bad cells in the grid.

You can move only in the right and down direction only. i.e. if you are on cell $(i, j)$, so you can move to $(i + 1, j)$ and $(i, j + 1)$.

You are asked to find the no of ways or no of unique paths to reach cell $(n, m)$ from cell $(1, 1)$. As the answer can be large print it modulo ${10^9 + 7}$.

#### Constraints:

${1 \le n, m\le 10^5}$, ${0 \le k \le min(10^3, n * m).}$

#### Sample Example

n = 5, m = 5, k = 2.

bad cells = (1, 2), (3, 3).

 » 21 month(s) ago, # | ← Rev. 2 →   +11 Hi,This is an identical problem from the AtCoder Educational DP contest, although with lower limits of $k$ (in this problem it is $3000$, while in your problem it is $10^6$).Update, your problem constraints have been fixed to $10^3$, so this is basically an identical problem now.