Snakes and Ladders
Akshay as a child was immensely in love with the board game Snakes and Ladders. As he grew up he designed a game of his own based on the same lines. The game rules that he framed were somewhat like this :
1. You start from the initial position ie the first square
2. At each step you have two choices
a. move to next square
b. take the ladder/snake if available at the square
3. The ladders/snakes are only unidirectional
4. There are no ladders from one square to its next consecutive one and no 2 ladders or snake has same start and end coordinates.
5. The game is played via a fixed no. of coupons that a player gets at the beginning of the game.
6. The objective is to reach the finishing square as well as finishing all the given k coupons
7. The player forfeits a coupon for each step that he takes.
For a given configuration of the Board Game and K coupuns, Akshay wants to find out the number of different possible ways to complete the game successfully. Help Akshay solve his dilemma.
The first line will contain a single integer d , the size of each side of the square board. Next line will contain l,the number of snakes and ladder in the board . Following l lines will contain 2 integer ai and bi each . Denoting their is ladder from ai to bi if bi > ai or a snake from ai to bi if ai > bi
The last line will contain k , the number of coupons.
output will contain a single integer denoting the number of different ways possible ( modulo 1000000007 )
Input: 2 1 2 4 2 Output: 1
Explanation of input
first number 2 means board is of size 2X2 . There is one ladder starting from 2 and end 4 and you can reach the last square ie 4 in 2 steps in only 1 way.
|Time Limit:||1.39498 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions