In class, we talked about solving a grid walking problem. For this project, we'll solve one question

with several parts by hand and then write a program to solve similar problems. Because the actual

answer for these problems can be very high, in your program, you'll report the answers modulo

$109+7.$ This will require the use of the type long long in C$.$ If you use Python, no special integer

type is needed. In class a similar $($but shorter$)$ project example will be done so you can see what is

expected of the program, format wise. $2)(85$ pts$)$ Write a program that will answer two types of grid walking queries that are described

in the examples above. $($a$)$ Given a starting location, an ending location, upto $5$ positions to visit, determines the number

of ways to go from start to end visiting each of the locations, modulo $109+7.$ Note: you must

handle the special case indicated in problem $1$d$.)($b$)$ Given a starting location, an ending location, and one or two positions to avoid, determines the

number of ways to go from start to end avoiding the given intermediate positions, modulo $109+7.$

$($This also has a special case similar to $1$d that must be properly coded.$)$

Your program will run without prompting the user but will read input from standard input and

produce output to standard output as specified below. Please write your program in C or Python.

Your program will be tested on multiple sets of input.