lalele

În curtea SEPI am plantat pe un singur rând lalele de $C$ culori. Vom considera, pentru simplitate, culorile numerotate de la $1$ la $C$. Dintre lalelele plantate au răsărit doar $N$ și acum au înflorit. Vom considera lalelele numerotate de la $1$ la $N$, în ordinea în care se află pe rând. Vrem să culegem un buchet în care să existe exact $K$ culori distincte.

Cerință

Scrieți un program care, cunoscând $N$, $C$, $K$, precum și culoarea fiecărei lalele, determină numărul de posibilități de a culege un buchet în care să apară exact $K$ culori distincte.

Date de intrare

Fișierul de intrare lalele.in conține pe prima linie numerele naturale $N \ C \ K$, cu semnificația din enunț. Pe cea de a doua linie se află $N$ numere naturale cuprinse între $1$ și $C$, $L_1 \ L_2 \ \ldots \ L_N$, reprezentând culorile lalelelor care au înflorit, în ordinea în care acestea au fost plantate pe rând. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire lalele.out conține o singură linie pe care este scris numărul de posibilități de a culege un buchet în care să apară exact $K$ culori distincte.

Restricții și precizări

• $2 \leq N \leq 500$;
• $1 \leq K \leq C \leq 50$;
• Două buchete sunt considerate distincte dacă există cel puțin o lalea care a fost culeasă într-un buchet, dar nu a fost culeasă și în celălalt.

Exemplu

lalele.in

6 4 2
4 1 2 1 1 2

lalele.out

31

Explicație

Pe rând există $6$ lalele, care au culori cuprinse între $1$ și $4$. Trebuie să determinăm toate posibilitățile de a culege un buchet în care apar exact două culori distincte. Posibilitățile sunt:

• $(1, 2)$, $(1, 2, 4)$, $(1, 2, 5)$, $(1, 2, 4, 5)$, $(1, 4)$, $(1, 4, 5)$, $(1, 5)$ (în aceste buchete culorile distincte sunt $1$ și $4$);
• $(1, 3)$, $(1, 6)$, $(1, 3, 6)$ (în aceste buchete culorile distincte sunt $2$ și $4$);
• $(2, 3)$, $(2, 3, 4)$, $(2, 3, 5)$, $(2, 3, 6)$, $(2, 3, 4, 5)$, $(2, 3, 4, 6)$, $(2, 3, 5, 6)$, $(2, 3, 4, 5, 6)$, $(2, 4, 5, 6)$, $(2, 4, 6)$, $(2, 5, 6)$, $(2, 6)$, $(3, 4)$, $(3, 4, 5)$, $(3, 4, 5, 6)$, $(3, 4, 6)$, $(3, 5)$, $(3, 5, 6)$, $(4, 6)$, $(4, 5, 6)$, $(5, 6)$ (în aceste buchete culorile distincte sunt $1$ și $2$).

În total: $31$ de posibilități.