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).

answer = 17.

Idea: Can you perhaps remove the amount of "bad routes" from all possible routes? How can this be done?

A similar problem: https://my.newtonschool.co/playground/code/dhw2vt31pdfp/ (Newton School July Contest Problem D)

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.

Thanks for your reply. I updated the constraints. Previous constraints were incorrect!