Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

У древном подруму Комисије за жалбе, налази се \(N\) гомила такмичарских жалби поређаних у низ - на \(i\)-тој гомили се налази \(a_i\) жалби. Дошло је време да се и те жалбе одбију па је Главни Архиватор Ђорђе Кавурмов добио задатак да подели гомиле члановима комисије. Кавурмов планира да подели ове гомиле жалби у хрпе (веће гомиле) - узастопне поднизове гомила жалби при чему ће свака гомила жалби припадати тачно једној хрпи (поднизу).

Међутим, то није тривијалан посао јер величине хрпи морају бити таман (акценат на друго ‘а’) тј. ни превелике ни премале. Прецизније, за сваку хрпу мора важити да њена величина (број гомила жалби у њој, тј. дужина подниза) није мања од најмање гомиле која јој припада (јер то нема смисла) и да није већа од највеће гомиле која јој припада (јер је то безвезе). Како Архиватор не воли да ради, он је одлучио да седи и размишља на колико начина може поделити дати низ гомила на хрпе. Заправо, одлучио је само да седи а размишљање препушта вама - као награду, проследиће вашу жалбу некоме ко их заправо чита пре одбијања.

Описи функција

Потребно је да имплементирате функцију

где је \(N\) - број гомила жалби док је \(a\) низ који описује гомиле жалби: \(i\)-та гомила садржи \(a_i\) жалби. Низ \(a\) је индексиран од 1. Ова функција мора да врати један цео број – тражени број подела по модулу \(1.000.000.007\) \((10^9 + 7)\). Обратити пажњу да решење мора бити у сегменту \([0, 10^9 + 6]\).

Пример

Нека је \(N = 7\) и \(a = [1, 6, 2, 3, 4, 3, 4]\). Тада је низ од ових 7 гомила жалби могуће поделити на хрпе на следећих \(6\) начина: | 1 | 6 2 3 4 3 4 |, | 1 6 2 | 3 4 3 4 |, | 1 6 2 3 | 4 3 4 |, | 1 | 6 2 | 3 4 3 4 |, | 1 | 6 2 3 | 4 3 4 |, | 1 6 | 2 3 | 4 3 4 |; дакле, у овом случају ваша функција мора вратити број \(6\) \(mod\) \((10^9 + 7)\) \(=\) \(6\). Обрадити пажњу да нпр. подела | 1 6 | 2 3 4 3 4 | није валидна јер је величина (дужина) десне хрпе \(5\) што је веће од највеће гомиле која јој припада (\(4\)); такође, подела | 1 6 2 | 3 4 | 3 4 | није валидна јер је величина последње две хрпе \(2\) што је мање од најмањих гомила које им припадају (у оба случаја \(3\)).

Ограничења

Подзадаци

Детаљи имплементације

Потребно је да пошаљете тачно један фајл taman.cpp или taman.pas, који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

У зависности од програмског језика који користите, ваша функција/процедура мора бити следећег облика:

Језик Декларација функције
C++ int TamanPodela(int N, int a[]);
Pascal function TamanPodela(N : longint; var a : array of longint) : longint;

Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

Тестирање и експериментисање

Уз задатак, обезбеђени су вам “template” фајлови code.cpp и code.pas које можете користити и мењати по потреби. Такође су вам обезбеђени програми grader.cpp, grader.pas који служе да лакше тестирате кодове. Ови програми учитавају са стандардног улаза следеће податке:

а затим позивају вашу функцију са учитаним параметрима и, на крају, вредност коју ваша функција враћа исписују на стандардни излаз. Кодове ових програма можете мењати по потреби.