Se consideră un şir de N numere naturale, precum şi 3 numere naturale M, A, B.

Cerinţă

Să se determine numărul de subşiruri crescătoare ale şirului dat care au suma elementelor modulo M cuprinsă între A şi B.
Mai exact, dat fiind şirul a=(a₁, a₂, ..., a_N), trebuie să determinăm numărul de subşiruri ale lui a (a_i1<= a_i2<= ...<= a_ik) (i₁<i₂<...<i_k) cu proprietatea că A≤S%M≤B, unde S= a_i1 + a_i2 + ... + a_ik.

Date de intrare

Fişierul de intrare subsiruri.in va conţine pe prima linie numerele naturale N M A B. Pe a doua linie se află N numere naturale reprezentând elementele şirului dat. Valorile scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire subsiruri.out va conţine o singură linie pe care va fi scris rezultatul modulo 666013.

Restricţii

• 1 ≤ N, M, A, B ≤ 1000
• Elementele şirului sunt numere naturale din intervalul [1, 1000]
• Pentru 40% din teste N ≤ 250 (Atenţie!!! M, A, B ≤ 1000).
• Un subşir are cel puţin un element.

Exemple

subsiruri.in	subsiruri.out	Explicaţii
3 13 5 10 34 29 23	2	Cele 2 subşiruri sunt : 34 ( 5 ≤ 34 % 13 ≤ 10) 23 (5 ≤ 23 % 13 ≤ 10)

Mircea Dima

Vrije Universiteit Amsterdam

blasterzm@gmail.com