InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

Unreliable Rover

Given a string A of size N describing the movement of a rover in the infinite matrix.
Fortunately we know the initial position of the rover in the matrix.You need to locate the final position of the rover.
Infinite matrix is divided into squares with side length 1 meter.
In this infinite matrix, In one step rover moves onto the next square in one of the four directions(North, South, East or West).


A[i] == ‘N’ Rover moves in the North direction

A[i] == ‘S’ Rover moves in the South direction

A[i] == ‘E’ Rover moves in the East direction

A[i] == ‘W’ Rover moves in the West direction

A[i] == ‘?’ we don’t know in which direction Rover is moving. It can be any of ‘N’, ‘S’, ‘E’ or ‘W’.

Two integer arrays B and C are given denoting the minimum and maximum steps taken by the rover
in A[i]th direction.

Find and return the area (in square meters) of the region where Rover can currently be located.

Since this area can be large return area modulo (109+7).

Note: Inital position of the rover does not change the answer.You can assume any initial position of the rover.

Input Format

The only argument given is the integer array A.

Output Format

Return the area modulo (10^9+7).


1 <= N <= 50
A[i] = {'N', 'S', 'E', 'W', '?'};
'?' can occur atmost 20 times in A
0 <= B[i] <= C[i] <= 10^7
if A[i] == '?':
    B[i] is 0

For Example

Input 1:
    A = "NE"
    B = [3, 3]
    C = [5, 5]

Output 1:
    Conidering initial position of rover as (0, 0).
    The rover ended at one of the cells (x,y) witn 3 <= x,y <= 5.

Input 2:
    A = "?"
    B = [0]
    C = [2]
Output 2:
    Conidering initial position of rover as (0, 0).
    The rover can end at any of the squares (-2,0), (-1,0), (0,-2), (0,-1), (0,0), (0,1), (0,2), (1,0), or (2,0).
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Unreliable Rover on Interview Code Editor
Sign Up
to access hints and editorial solutions for Unreliable Rover


Click here to start solving coding interview questions