, 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:-

Source code, processing two jobs through 2 machine

processing two jobs through 2 machine

Area under curve, Write a program to find the area under the curve y = f(x)...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b

Create cpp code for identify objects and their relationships, You are setti...

You are setting up an information system for a DVD Rental Company called Box office. The new system need to hold information about customers and DVDs rentals, payments and fines. C

Loops, how do i print out invalid input?

how do i print out invalid input?

Do i have to check for null after p = new fred()?, A: No. (Excluding if you...

A: No. (Excluding if you have an old compiler, you might have to force the new operator to throw an exception if it runs out of memory.) This turns out to be a real pain to alwa

Area of curve, Write a program to find the area under the curve y = f(x) be...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Change to palindrome, A palindrome is a string that reads the same from bot...

A palindrome is a string that reads the same from both the ends. Given a string S convert it to a palindrome by doing character replacement. Your task is to convert S to palindrome

Overloading binary operators using friend function, Overloading Binary Oper...

Overloading Binary Operators Using Friend Function class SI {float i,p,n,r,a; public: SI(){}; SI(int gp,int gn, int gr); void putdata(void); friend SI operato

C program for select the char which u want , C Program for SELECT THE CHAR ...

C Program for SELECT THE CHAR WHICH U WANT #include stdio.h> #include conio.h> void main() {             void substr(char[], int *, int *);           int a,b

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