Description

在一个Anniversary Ceremony上，有一个节目是需要n个男生和n个女生一对一手拉手有序地走进会场（也就是男生排成一列，女生排成一列，对位拉手）。这其中有m(m<=n)对是情侣。导演决定，情侣之间不能对位！有女朋友的男生不爽了，但是导演之命不可违，只能退而求其次，安排的顺序必须使得男生能够看到他的女朋友（也就是说，如果男生在第r列，那么他得女朋友必须在1~r-1列里面）。

帮导演算算这样的话，还有多少种可行的方案数吧。结果模1000000007;

Input

多组数据.每组数据， 第一行两个整数n,m(1<=m<=n<=1000). 然后是m行,每行两个整数bi,gi,表示bi号男和gi号女是情侣关系。(数据保证每个男/女生最多只有一个女/男朋友)。 (1<=bi, gi<=n)

Output

输出格式见样例，答案取模1000000007(i.e., 10^9+7)

Sample

Input

2 1
1 2

3 1
1 3

6 2
1 2
4 3

Output

Case 1: 1
Case 2: 12
Case 3: 74880

Hint

样例1共有4中方案{b1g1,b2g2}, {b2g2,b1g1}, {b1g2, b2g1}, {b2g1, b1g2};其中只有{b2g2, b1g1}是可行的. b=boy, g=girl.

Source: zjut_DD