Soluții trimise

În Sosmania sunt N fabrici de sos, numerotate de la 1 la N. Aceste fabrici folosesc pentru prepararea sosului o mulțime proprie de ingrediente. La nivel național, sunt acceptate M tipuri de ingrediente, numerotate de la 1 la M. Se consideră că o secvență formată din două sau mai multe fabrici este compatibilă, dacă toate fabricile din secvență folosesc cel puțin un ingredient comun. O secvență de fabrici (i, j) (1 ≤ i < j ≤ n) este formată din toate fabricile care au numărul de ordine x astfel încât i ≤ x ≤ j. Cunoscându-se N, M și mulțimea ingredientelor folosite de fiecare dintre cele N fabrici, să se determine numărul de subsecvențe compatibile.