The King of Zyorg has a cabinet with N ministers and they have assembled for a meeting. The King enters the meeting chamber to find that the ministers have arranged themselves so that friends sit with friends.

The seats are numbered 1 . . . N and we refer to the minister sitting on the i th seat in this initial arrangment as i. So, the initial arrangment is of the ministers is (1, 2, 3 . . . N).

The King orders the ministers to rearrange themselves and finds that some of the friends have just exchanged seats. The enraged King then orders that they must rearrange themselves so that for every k < N the set of ministers sitting in the first k chairs DOES NOT consist only of the ministers 1, 2, . . . k.

He then wonders if this is possible at all and quickly convinces himself that this is so. Then he wonders how many different ways can they rearrange themselves fulfilling his order.

For example, suppose N = 3. The initial arrangment is of course (1, 2, 3). If they rearrange themselves as (2, 1, 3) this will violate the King’s order because for k = 2 the ministers in positions 1 upto 2 are {1, 2}. On the other hand the arrangement (3, 1, 2) fulfils the requirement. For k = 1 we have {3}, for k = 2 we have {3, 1}. You can check that there are exactly 3 arrangments that comply with the King’s order. They are : (2, 3, 1),(3, 1, 2) and (3, 2, 1). So, for N = 3 the answer to this problem is 3.

Your task is to write out the answers for 3 values of N.

(a) N = 5

(b) N = 6

(c) N = 7