Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

GRNUM - Đánh số đồ thị

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/grnum


Cho một đơn đồ thị vô hướng gồm K x N đỉnh, các đỉnh được chia thành K nhóm, mỗi nhóm có N đỉnh. Các nhóm được đặt tên bằng các chữ cái in hoa A, B, C, ... các đỉnh tương ứng thuộc các nhóm được đặt tên bằng các số từ 0 đến N – 1. Giả sử ChK là chữ cái ứng với nhóm thứ K, ta quy ước chữ cái tiếp sau A là B, tiếp sau B là C, … tiếp sau ChK là A và ký hiệu chữ cái tiếp sau Ch là next(Ch). Đồ thị này có các tính chất sau:

Giữa các đỉnh thuộc cùng một nhóm không có cạnh nối.

Các đỉnh thuộc 2 nhóm bất kỳ có tên là Ch và next(Ch) có đúng N cạnh nối từ đỉnh thuộc nhóm Ch đến đỉnh thuộc nhóm next(Ch).

Bạn cần được yêu cầu đánh số các đỉnh của đồ thị sao cho:

Các đỉnh thuộc 1 nhóm được đánh các số là hoán vị của các số tự nhiên từ 0 đến N – 1.

Với 2 nhóm Ch và next(Ch) bất kỳ thì N số trên N cạnh nối các đỉnh thuộc chúng là khác nhau. Nếu đỉnh i thuộc nhóm Ch được đánh số là P kề với đỉnh j thuộc nhóm next(Ch) được đánh số là Q thì cạnh nối 2 đỉnh này được đánh số là (N + P – Q) mod N.

Biết rằng 2 cách đánh số các đỉnh của đồ thị được coi là khác nhau nếu trong 2 cách đánh số, tồn tại một đỉnh thuộc một nhóm nào đó được đánh số khác nhau. Bạn hãy tính số cách đánh số khác nhau.

Input

Dòng thứ nhất ghi 2 số nguyên dương K và N là số nhóm và số đỉnh thuộc 1 nhóm.

Mỗi dòng trong K x N dòng tiếp theo ghi 1 cạnh của đồ thị theo dạng Ch i j trong đó Ch là một ký tự, i và j là 2 số nguyên với ý nghĩ có cạnh nối từ đỉnh i của nhóm Ch đến đỉnh j của nhóm next(Ch).

Output

Ghi ra duy nhất một số nguyên là số lượng cách đánh số khác nhau tìm được.

Example

Input:
3 3
A 0 0
A 1 2
A 2 1
B 1 0
B 1 2
B 2 2
C 0 2
C 1 1
C 1 2

Output:
54

Giới hạn:
1 ≤ K ≤ 5
1 ≤ N ≤ 20
Số cách đánh số khác nhau luôn đảm bảo không quá 1000000


Được gửi lên bởi:special_one
Ngày:2008-10-18
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Ioicamp - marathon 06 - 07

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.