Hard Search Techniques > Meet in the middle

You lost on the grid-land which is a square grid of size **N*N**, where each position of the grid contains some amount of gold on it. You are now standing on position (1, 1) .You want to escape from grid-land to go to your home. The moves you can perform are either **“one step right”** or **“one step down”** as long as you are inside the grid-land. ![enter image description here][1] To escape from grid-land you have to reach at position (N, N) of the grid by fulfilling a condition. The condition is that the multiplication of all golds taken at different positions of grid during the move must be less than or equal to **K**. Input: ------ Input starts with an integer **T (1<=T<=10)** , denoting the number of test cases. Each case contains an integer **N (2 ≤ N ≤ 16)** denoting the size of grid-land. The next N lines will contain N integer each separated by single space, denoting the gold on respective position of grid. Next line contain an integer K as described in the problem statement. The value of gold in grid cell and K will be a positive integer at most **10^18**. Output: ------- For each case of input, output an integer denoting total number of ways to escape from grid-land by using constraint as describe above.As answer could be very large output it modulo **1000000007** Sample Input ------------ 1 2 2 2 2 2 100 Sample Output ------------- 2 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/2bb5711a-9287-c4c3-d039-08d458052dd7_3e08b274ce994de7964626aa0bc286c9_W256xH276.png

Bishal Gautam