Take as input N, the size of a chess board. We are asked to place N number of Knights in it, so that no knight can kill other.

a. Write a recursive function which returns the count of different distinct ways the knights can be placed across the board. Print the value returned.

b.Write a recursive function which prints all valid configurations (void is the return type for function).

Input Format:

Enter the size of the chessboard N

Constraints:

None

Output Format:

Display the number of ways a knight can be placed and print all the possible arrangements in a space separated manner

Sample Input:

2

Sample Output:

6

{0-0} {0-1} {0-0} {1-0} {0-0} {1-1} {0-1} {1-0} {0-1} {1-1} {1-0} {1-1}