POLSKI SPOJ

Bob Graham Round to wyzwanie biegowe polegające na zdobyciu 42 najwyższych szczytów Krainy Jezior, w północno-zachodniej Anglii, w 24 godziny.

Obecnie m osób planuje zmierzyć się ze zmodyfikowaną wersją tego wyzwania. Chcą oni zdobyć n najwyższych wierzchołków Krainy Jezior w 24 godziny. Szczyty zostały oznaczone numerami od 1 do n. Kolejność ich przejścia jest dowolna. Każda z m osób zapisała porządek w jakim będzie zdobywać wierzchołki.

Maciej chce przygotować relację filmową z tego wydarzenia. Zależy mu na sfilmowaniu wszystkich biegaczek i biegaczy. W związku z tym interesuje go, na ile sposobów można wybrać niepusty fragment pierwszej trasy, który występuje również w pozostałych m-1?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite m ∈ [2, 10] i n ∈ [1, 10⁴] oznaczające odpowiednio liczbę osób i liczbę szczytów do zdobycia.

W kolejnych m liniach znajdują się opisy każdej z m tras przygotowanych przez biegaczki i biegaczy. Opis każdej trasy to permutacja liczb od 1 do n określająca kolejność przejścia wierzchołków.

Wyjście

Na wyjściu należy wypisać, na ile sposobów można wybrać niepusty fragment pierwszej trasy, który występuje również w pozostałych m-1.

Przykład

Wejście:

3 7
1 2 3 4 5 6 7
7 6 5 2 3 4 1
2 3 4 7 1 6 5

Wyjście:

10

Wyjaśnienie do przykładu:

Fragmenty pierwszej trasy, które występują również w m-1 pozostałych to:

• 1
• 2
• 2-3
• 2-3-4
• 3
• 3-4
• 4
• 5
• 6
• 7