После долги години поминати во учење, Мендо одлучил да стане професор. На еден од своите часови, тој спровел тест. Класот на професорот Мендо се состои од N ученици, и притоа i - тиот ученик освоил A_i поени на тестот.

Мендо го гледа списокот со резултатите на учениците и сака да формира група т.ш. ќе нема најлош ученик (за да нема понижувања) и резултатите на учениците во групата ќе се соседни во списокот. Со други зборови, од низата со резултати (освоени поени) на учениците, тој сака да издвои континуирана подниза во која нема уникатен (единствен) минимум на поени. На колку начини може да го направи тоа Мендо?

Влез

Во првата линија од влезот е даден еден цел број N (0 < N ≤ 200 000) - бројот на ученици во класот на Мендо.
Втората линија содржи N цели броеви A_i (0 ≤ A_i < 10⁹), разделени со по едно празно место - поените освоени на спроведениот тест од страна на учениците.
Забелешка. За 50 поени ќе важи: N ≤ 1 000

Излез

Отпечатете еден цел број - бројот на начини на кои Мендо може да ја формира посакуваната група од ученици. Бидејќи овој број може да биде многу голем, да се отпечати по модул 1 000 000 007.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 16 megabytes

Примери

влез
5
1 2 2 1 1

излез
6

Објаснување за примерот: Мендо може да ги формира следниве 6 групи: (1, 2, 2, 1); (1, 2, 2, 1, 1); (2, 2); (2, 2, 1, 1); (2, 1, 1); (1, 1).