Printful Draugu grupai ir 2 X n tabula, un a_i skaitļi ar vērtību i. Zināms, ka a₁ + ... + a_n = 2n. Cik veidos var aizpildīt tabulu ar šiem skaitļiem tā, lai gan katrā rindā, gan katrā kolonnā skaitļi atrastos sakārtotā secībā?

Divi tabulu aizpildīšanas veidi tiek uzskatīti par dažādiem, ja ir vismaz viena rūtiņa, kur atšķiras ierakstītie skaitļi.

Pirmajā rindā dots viens naturāls skaitlis n, tabulas platums (1 <= n <= 10⁴). Nākamajā rindā doti n naturāli skaitļi a₁, ..., a_n, doto skaitļu skaiti (0 <= a_i <= 2n). Garantēts, ka a₁ + ... + a_n = 2n.

Izvadiet vienu veselu skaitli, dažādu veidu skaitu pēc moduļā 10⁹+7.

Apakšuzdevumi:

* n <= 5 - 10 punkti;
* n <= 10 - 20 punkti;
* n <= 1000 - 40 punkti;
* bez ierobežojumiem - 30 punkti;

Pirmajā testa piemērā izvietot skaitļus var tikai šādos divos veidos: 

11221212

Otrajā testa piemērā eksistē šādi divi veidi:

123233122333