Given a square maze (A) of dimension N, every entry (Aij) in the maze is either an open cell 'O' or a wall 'X'. A rat can travel to its adjacent locations (left, right, top and bottom), but to reach a cell, it must be open. Every cell in the maze will contain a survival probability P.
Your task is to find the number of ways to place maximum number of rats, such that they are not able to reach other and at the same time their minimum survival probability is at least PS. As the result can be long, take modulus of the result with 1000000007