Hotel |
Solution |
Tests |

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.

Task

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

Input format

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,

Output format

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

Restrictions

- 1 <= n <= 1000
- The number of floors from the hotel <= 200
- 1 <= k <=200

Examples

HOTEL.IN 4 5 123 2 35 1 430 2 13 0 |
HOTEL.OUT 60 |

HOTEL.IN 5 2 12 1 13 0 14 1 10 2 11 0 |
HOTEL.OUT 0 |

Time limit: 1 second/test