Masuri Disperate

Cerință

Clopotel se afla in mijlocul sediului BGK, adus acolo de toate dovezile gasite pana acum. El are o singura misiune, cea de a-l gasi pe misteriosul Perseus, sub indrumarea lui Russell Adler.

$\\$
Ei doi se inflitreaza in sediu, ajutati de contactul lor, Dimitri Belikov. Dar acesta, dupa ce a sacrificat atat de multe pentru a-i aduce pe ei in inima informatiei sovietice, doreste ceva la schimb.

$\\$
Dinainte, Clopotel stie o informatie foarte importanta. Pentru un sir oarecare A de lungime K, importanta sa este definita ca numarul de indici i cu $2 \leq i \leq k$, cu proprietatea ca $A_i > A_{i-1}$.

$\\$
Belikov le da un sir de N elemente, $P_1, P_2, ... P_n$. El are nevoie de doua raspunsuri de la ei, si doua raspunsuri rapide, asa ca le ofera T, cerinta, care poate fi 1 sau 2.

$\\$
Pentru T = 1, el alege fiecare subset de indici $i_1, i_2, ... , i_k$, si calculeaza importanta subsetului $P_{i_1}, P_{i_2}, ... , P_{i_k}$. Raspunsul final este suma lor, modulo $10^9 + 7$, un cod important in randul ofiterilor.

$\\$
Pentru T = 2, Dimitri are o rugaminte mai lunga. El, initial, scrie pe o foaie toate sirurile L de N elemente, $L_1 ... L_n$ cu proprietatea ca $1 \leq L_i \leq P_i$. Apoi repeta procesul de la T = 1, generand fiecare subset de indici al fiecarui sir L si insumand importantele lor. Clopotel trebuie sa spuna aceasta suma, modulo $10^9 + 7$.

$\\$
Belikor ar fi foarte multumit de treaba lui Clopotel si Adler, dar ei sunt soldati foarte buni, nu informaticieni. Cei doi nu stiu sa rezolve problema, asa ca apeleaza la tine sa ii ajuti.

Date de intrare

Pe prima linie a fișierului de intrare masuri-disperate.in se gaseste numarul T, reprezentand cerinta, urmat de N pe a doua linie si sirul P pe a treia.

Date de ieșire

Pe prima linie a fișierului de ieșire masuri-disperate.out se va găsi un singur număr întreg, reprezentant solutia problemei, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• $1 \leq P_i \leq 1 \ 000 \ 000$
• $1 \leq T \leq 2$

Subtaskuri

Pentru T = 1 (33 puncte) :

• Pentru 11 puncte, $1 \leq N \leq 7$
• Pentru alte 22 puncte, $8 \leq N \leq 1 \ 000$

Pentru T = 2 (67 puncte) :

• Pentru 20 puncte, $1 \leq N \leq 7$ si $1 \leq P_i \leq 3$
• Pentru 20 puncte, $1 \leq P_i \leq 100$
• Pentru alte 27 puncte, $8 \leq N \leq 1 \ 000$

Exemplul 1

masuri-disperate.in

1
3
3 6 4

masuri-disperate.out

3

Explicație

Se vor alege submutimile de indici cu corespondentele lor:
{1, 2} $\rightarrow$ {3, 6}, valoare = 1
{1, 3} $\rightarrow$ {3, 4}, valoare = 1
{2, 3} $\rightarrow$ {6, 4}, valoare = 0
{1, 2, 3} $\rightarrow$ {3, 6, 4}, valoare = 1

Suma lor, modulo $10^9 + 7$, este 3.

Exemplul 2

masuri-disperate.in

2
3
1 2 2

masuri-disperate.out

8

Explicație

Sirurile L posibile sunt:
{1, 1, 1}, care are subseturile:
{1, 2} $\rightarrow$ are valoarea 0
{1, 3} $\rightarrow$ are valoarea 0
{2, 3} $\rightarrow$ are valoarea 0
{1, 2, 3} $\rightarrow$ are valoarea 0

{1, 1, 2}, care are subseturile:
{1, 2} $\rightarrow$ are valoarea 0
{1, 3} $\rightarrow$ are valoarea 1
{2, 3} $\rightarrow$ are valoarea 1
{1, 2, 3} $\rightarrow$ are valoarea 1

{1, 2, 1}, care are subseturile:
{1, 2} $\rightarrow$ are valoarea 1
{1, 3} $\rightarrow$ are valoarea 0
{2, 3} $\rightarrow$ are valoarea 0
{1, 2, 3} $\rightarrow$ are valoarea 1

{1, 2, 2}, care are subseturile:
{1, 2} $\rightarrow$ are valoarea 1
{1, 3} $\rightarrow$ are valoarea 1
{2, 3} $\rightarrow$ are valoarea 0
{1, 2, 3} $\rightarrow$ are valoarea 1

masuri-disperate.in

2
6
1 2 7 6 3 5

masuri-disperate.out

82188