[INOI1401] Highway Bypass (INOI 2014: India)

Problem in short: In a grid of size R x C, you need to find the number of paths from the top-left to the bottom-right. You may only move 1 block to the right or one block down in each step. You may not go through any blocked intersections (given), and you may take at most d consecutive steps in the same direction. R, C <= 300.

Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.