Migrated from Lutece 140 Triangles

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Mr. Cooper was a celebrated scientist who had a really big lab. There were $N$ sticks in this lab and the length of the $i_{th}$ stick was $i$ millimeters. One day, when Mr. Cooper decided to do research on triangles, he found that $M$ of the sticks were missed. Mr. Cooper wanted to know how many kinds of triangles could be constructed by three of the remaining sticks. Two triangles are different if and only if they are formed by different sets of sticks.

For Example, there were $8$ sticks in the lab originally and the second and the sixth sticks were missed. The $7$ different triangles can be constructed were 3,4,5, 3,5,7, 4,5,7, 3,7,8, 4,7,8, 5,7,8, 4,5,8.

Input

The first line contains an integer $T$ ($T\leq 25$) indicating the number of test cases. The first line of each test case contains two integers $N$ ($1\leq N\leq 1000000000$) and $M$ ($0\leq M\leq 1000$). If $M$ is not zero, there is an additional line containing $M$ distinct integers between $1$ and $N$ indicating the missed sticks.

Output

For each test case, print the case number and the answer mod $1000000007$ in a single line where the answer is the number of the triangles can be formed. Please follow the format of the sample output.

Samples

3 
3 0 
8 2 
2 6 
58 3 
23 5 3

Case 1: 0 
Case 2: 7 
Case 3: 13861

Resources

The 5th Guangting Cup Central China Invitatio