#11067Little Red Riding Hood

You probably all know the fairy tale of Little Red Riding Hood and how she wanted to visit her grandmother, but on her way there met a wolf, finally got eaten by the wolf and was rescued in the end by a brave hunter. Now if Little Red Riding Hood hadn't met the wolf in the first place, she would have avoided a lot of hassle (she wouldn't have been eaten by the wolf and the brave hunter wouldn't have had to rescue her). That she met the wolf in the first place was partly due to her lack of information. She simply didn't know where she might encounter the wolf.

The network of roads connecting Little Red Riding Hood's house and her grandmother's house is a rectangular grid. Little Red Riding Hood's house is situated on the grid's lower left corner and her grandmother's house is at the grid's top right corner. Being particularly bright at math Little Red Riding Hood always wants to get to her grandmother using the shortest possible route. This entails that Little Red Riding Hood can only "move" to right or upwards on the grid. This ensures that she always uses a shortest route. Now if she had known the wolf's possible locations in advance, she might have chosen a path on which she doesn't meet the wolf.

Now given the size of the grid and the wolf's possible locations (weirdly enough the wolf can only meet her at the grid's intersections) compute the number of possible paths from Little Red Riding Hood's house to her grandmother's house under the restriction that Little Red Riding Hood can only move to the right and upwards and does not meet the wolf.

1 1
0
1 1
2
0 1
1 0
4 4
3
0 1
1 1
3 1
10 10
0
10 10
3
0 1
1 1
1 0
3 3
5
1 0
1 1
1 2
2 2
3 2
0 0

There are 2 paths from Little Red Riding Hood's house to her grandmother's house.
There is no path.
There are 7 paths from Little Red Riding Hood's house to her grandmother's house.
There are 184756 paths from Little Red Riding Hood's house to her grandmother's house.
There is no path.
There is one path from Little Red Riding Hood's house to her grandmother's house.