Teacher of Math prepared N samples for pupils with arithmetical actions +, -, *, : for certification. Every sample has some quantity of arithmetical actions. For receive certification every pupil must solve K samples from list, but you must use that way where every sample with more number from list has more quantity of arithmetical actions.

   How many ways you can create from list, that every way have K sample.

   Input

   First line of input file has two numbers: N is a quantity of samples, which prepared the teacher, and K is quantity of samples, which you must solve for pass an examination.

   Next we have N lines, which number is equal to number of problem and have one sample with arithmetical actions +, -, *, :.

   1 ≤ K ≤ 100, 1 ≤ N ≤ 100. The quantity of arithmetical actions in sample does not exceed 1000.

   Output

   One number is quantity of differences ways. Two different ways must be differ one problem even if. If you can create any ways, than output -1.