SP10440 FRNDS - Friends

Friends A group of N people are going to the movies, some pair of them are friends and according to the famous saying that "The friends of my friends are my friends, too" it follows that if A and B are friends and B and C are friends then A and C are friends, and do not forget that every friendship is mutual, if A is friend of B, then B is also friend of A. They will all sit in the first row at the cinema, there are N seats in each row, a way is good if there is at least one pair of of people that are friends and at the same time they are sitting in adjacent seats. So that is your task, to count how many assignments of those N people in the N seats are good.

Input starts with an integer T (1

For each test case print a single line with "Case #X: P" where X is the number of the test case (starting from 1) and P is the number of ways modulo 1000000007. Look at the sample output for more details.