Subsir100

subsir100

== include(page="template/taskheader" task_id="subsir100") ==

Andreea a primit de la prietena sa Ioana un sir format din $N$ numere naturale. Deoarece Ioanei ii plac subsirurile interesante, ea a rugat-o pe Andreea sa numere cate subsiruri interesante distincte contine sirul de numere. Un subsir este interesant daca oricare doua numere din subsir sunt diferite intre ele. Pentru ca numarul de subsiruri interesante poate fi mare, Andreea va cere sa aflati doar restul impartirii acestui numar la $1000003$.

Andreea a primit de la prietena sa Ioana un sir format din $N$ numere naturale. Deoarece Ioanei ii plac subsirurile $interesante$, ea a rugat-o pe Andreea sa numere cate subsiruri $interesante$ contine sirul de numere. Un subsir este $interesant$ daca contine doar numere distincte. Pentru ca numarul de subsiruri $interesante$ poate fi mare, Andreea va cere sa aflati doar restul impartirii acestui numar la $1000003$.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $subsir100.out$ se va afla numarul total de subsiruri interesante, modulo $1000003$.

În fişierul de ieşire $subsir100.out$ se va afla numarul total de subsiruri $interesante$, modulo $1000003$.

h2. Restricţii
* $1 ≤ N ≤ 100 000$
* Numere din sir sunt numere naturale mai mici decat $2 000 000 000$.

* Considerand ca sirul dat este {$A=(a{~1~},a{~2~}...a{~N~})$}, se numeste subsir al lui $A$ un sir {$B=(a{~i{~1~}~},a{~i{~2~}~}...a{~i{~K~}~})$} cu proprietatea $1 &le; i{~1~} < i{~2~} < ... < i{~K~} &le; N$.
* Doua subsiruri {$B=(b{~i{~1~}~},b{~i{~2~}~}...b{~i{~K~}~})$} si {$C=(c{~j{~1~}~},c{~j{~2~}~}...c{~j{~P~}~})$} sunt distincte daca $K$ este diferit de $P$ sau exista $q$ astfel incat $i{~q~}$ sa fie diferit de $j{~q~}$.

* Considerand ca sirul dat este {$A=(a{~1~},a{~2~}...a{~N~})$}, se numeste subsir al lui $A$ un sir {$B=(b{~i{~1~}~},b{~i{~2~}~}...b{~i{~N~}~})$} cu proprietatea $1 &le; i{~1~} < i{~2~} < ... < i{~K~} &le; N$.

h2. Exemplu

h3. Explicaţie

Cele $5$ subsiruri $interesante$ sunt marcate ingrosat: $*1* 1 2$, $1 *1* 2$, $1 1 *2*$, $*1* 1 *2*$ si $1 *1* *2*$.

Cele $5$ subsiruri $interesante$ sunt: $1$, $2$, $1 1$, $1 2$ si $1 1 2$.

== include(page="template/taskfooter" task_id="subsir100") ==

3887