import Data.List
main=interact $ show.f.lines
f::[String]->Integer
f (nm:aaa:_) = sum $ map (g.genericLength) $ group $ sort $ map (flip mod m) $ map sum $ inits $ map read $ words aaa
    where m = read $ head $ tail $ words nm
g::Integer->Integer
g x = div (x*(x-1)) 2