implementare

Se consideră algoritmul:

citeşte  k , n; 
s = 0; 
for (i1 = 1 ; i1 ≤ k ; i1++) 
	for (i2 = 1 ; i2 ≤ i1 ; i2++) 
		for (i3 = 1 ; i3 ≤ i2 ; i3++) 
			........................................ 
				for (in = 1 ; in ≤ in-1 ; in++) 
					s = s + in; 
scrie s; 
stop.

Cerinţă

Să se scrie un program care implementează algoritmul de mai sus.

Date de intrare

Fişierul de intrare implementare.in conţine două numere naturale nenule $k$ şi $n$ separate printr-un spaţiu, cu semnificaţiile de mai sus.

Date de ieşire

Fişierul de ieşire implementare.out va conţine pe prima linie restul împărţirii valorii $s$, calculate de algoritm, la $666 \ 013$.

Restricții și precizări

• $1 \leq k , n \leq 50 \ 000$;
• $40\%$ din teste au k şi n $\leq 500$;
• $20\%$ din teste au k şi n $\geq 5 \ 000$;

Exemplul 1

implementare.in

3 2

implementare.out

10

Explicație

$k=3$ şi $n=2$. Prima instrucţiune for se execută pentru toate valorile contorului său $i_1$ cuprinse între $1$ şi $3$ şi algoritmul va conţine exact $2$ instrucţiuni for imbricate. A doua instrucţiune for se execută pentru toate valorile contorului său $i_2$ cuprinse între $1$ şi $i_1$ şi calculează prima dată $1$ apoi $1+2$ şi în final $1+2+3$. Suma totală calculată de algoritm este $10$.