Score : 1600 points
Joisino has a bar of length N, which has M marks on it. The distance from the left end of the bar to the i-th mark is X_i.
She will place several squares on this bar. Here, the following conditions must be met:
Examples of arrangements that satisfy/violate the conditions
The beauty of an arrangement of squares is defined as the product of the areas of all the squares placed. Joisino is interested in the sum of the beauty over all possible arrangements that satisfy the conditions. Write a program to find it. Since it can be extremely large, print the sum modulo 10^9+7.
Input is given from Standard Input in the following format:
N M X_1 X_2 ... X_{M-1} X_M
Print the sum of the beauty over all possible arrangements that satisfy the conditions, modulo 10^9+7.
3 1 2
13
There are two possible arrangements:
The sum of the beauty of these arrangements is (1 \times 1 \times 2 \times 2) + (3 \times 3) = 13.
5 2 2 3
66
10 9 1 2 3 4 5 6 7 8 9
100
1000000000 0
693316425