There are n employees in a hotel, in the Administrative Department. The hotel’s employer decides to change the personnel’s outfit from this department as follows: the employees that work at different floors to have costumes with a different color and the employees that work at the same floors to have costumes with the same color. Every employee has a unique code, a natural number, which has a maximum of 4 digits.

Find a solution for choosing the color of the costumes which respects these conditions and also the number of possibilities.

The input file HOTEL.IN contains:

• On the first line – 2 natural numbers, n and k separated by a space character ( k is the number of colors )
• On the next n lines there are, two by two, 2 natural numbers, separated by a space character; the first number is the code, and the other is the number of the employee’s floor.

The line of the output file HOTEL.OUT will contain the number of the modalities.