URI Online Judge | 2599

Counting Radars

By Abner Samuel P. Palmeira, IFSULDEMINAS BR Brazil

Timelimit: 3

Taxilândia's government is facing a huge problem, the people of Taxilândia love cars and speed, so they are running a lot in the avenues of the city. To mitigate  this problem the government will install radars on the avenues, so that each section is covered by a radar. The company that the government contracted has M types of radars available, each of which covers Mi kilometers adjoining the avenue.

You have been hired by the government to make a program that, given the length of the avenue and the radar coverage area, state how many different ways you can put the radars on the avenue so that it is fully populated.

The image below shows an avenue of size 4 miles and radars with coverage of 3 and 2 kilometers, each color represents a radar, so it is possible to notice that the distinct amount of cover the avenue are 4.

Input

The first line of the entry is made up of an integer C that represents the number of test cases. The first line of each test case has two integers and M which indicate the size of the avenue and how many radar sizes are available on the market.

The second line is composed of M integers representing the size of the available radars.

(1 ≤ N ≤ 104)

(1 ≤ M ≤ 103)

(1 ≤ Mi ≤ N)

Output

Your program should display the number of distinct ways to cover the entire avenue. Output the anwser modulo 109 + 7.

Input Sample Output Sample

1
4 2

3 2

4