, C/C++ Programming

Assignment Help:
Question 1 / 1
You have an N x N chessboard and you wish to place N kings on it. Each row and column should contain exactly one king, and no two kings should attack each other (two kings attack each other if they are present in squares which share a corner).

The kings in the first K rows of the board have already been placed. You are given the positions of these kings as an array pos[ ]. pos[i] is the column in which the king in the ith row has already been placed. All indices are 0-indexed. In how many ways can the remaining kings be placed?

Input:
The first line contains the number of test cases T. T test cases follow. Each test case contains N and K on the first line, followed by a line having K integers, denoting the array pos[ ] as described above.

Output:
Output the number of ways to place kings in the remaining rows satisfying the above conditions. Output all numbers modulo 1000000007.

Constraints:
1 <= T <= 20
1 <= N <= 16
0 <= K <= N
0 <= pos_i < N
The kings specified in the input will be in different columns and not attack each other.

Sample Input:
5
4 1
2
3 0

5 2
1 3
4 4
1 3 0 2
6 1
2

Sample Output:
1
0
2
1
18

Explanation:
For the first example, there is a king already placed at row 0 and column 2. The king in the second row must belong to column 0. The king in the third row must belong to column 3, and the last king must beong to column 1. Thus there is only 1 valid placement.

For the second example, there is no valid placement.

Related Discussions:-

Solve system of linear equations-gaussian elimination , Write a C function ...

Write a C function to solve the system of linear equations A x = y where A is an N by N matrix in the format of pointer-to-pointers and y is a vector in the format of a pointer. Th

Wap to print the largest number from any 10 numbers, WAP TO PRINT THE LARGE...

WAP TO PRINT THE LARGEST NUMBER FROM ANY 10 NUMBERS #include stdio.h> #include conio.h>   void main()   {                    int a[10],i,max;

What is some instance of operator overloading?, A: Here are a few of the ma...

A: Here are a few of the many instance of operator overloading: myString + yourString may concatenate two std::string objects myDate++ may increment a Date object a * b may m

Boardcoloring, In this problem you are given a board in which some of the e...

In this problem you are given a board in which some of the elements are placed as shown in diagram below. Each element represents a color. Fill the other elements in the board, suc

Luminous Jewels - The Polishing Game, Byteland county is very famous for lu...

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

Program is to perform string operations, Program is to perform string opera...

Program is to perform string operations: Program is to perform string operation without using in built functions using classes and object void mainmenu()    {    clrs

Define passing by reference?, A: Method of passing arguments to a function ...

A: Method of passing arguments to a function that takes parameter of type reference.  for instance: void swap( int & x, int &amp;amp; y ) { int temp = x; x =

Write a program to create a binary file, Write a program to create a binary...

Write a program to create a binary file and store the following data "hello", 0x0030,'1', 1.234  Using visual studio examine the binary file and note how the day is stored   Answe

Algorithme, algorithm to find whether a given number is prime number or not...

algorithm to find whether a given number is prime number or not? using pseudo code and flowchart

Help, what is c++ ?

what is c++ ?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd