АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Фермер Жонд Holsteins, Jerseys,болон Guernseys гэсэн гурван үүлдрийн N (2 <= N <= 15) ширхэг үнээ байгаа.

Харамсалтай нь Фермер Жон үнээнүүдийхээ ямар ямар үүлдрийнх гэдгийг мартсан. Гэсэн ч түүнд K (1 <= K <= 50) ширхэг үнээнүүдийн хамаарлыг агуулах жагсаалт байгаа. Жишээ нь 1 болон 2-р үнээнүүд ижил үүлдэр, эсвэл 1 болон 5-р үнээнүүд өөр үүлдрийнх гэх мэт.

Танд Фермер Жоны жагсаалт байгаа бол түүнд боломжит бүх үүлдэр оноолтын тоог олоход нь тусална уу.

Input

Эхний мөр: Зайгаар тусгаарлагдсан N болон K бүхэл тоонууд.

Хоёроос (1 + K)-р мөр: Мөр болгон хоёр үнээний дугаар болох x болон y бүхэл тоонууд (1 <= x,y <= N, x != y) агуулна. Хэрэв "S x y" гэсэн бол x болон y дугаар үнээнүүд ижил үүлдрийнх харин "D x y" бол өөр үүлдрийнх гэсэн үг.

Output

Эхний мөр: Бодлогын хариу болох ганц бүхэл тоо.

Example

Input:

4 2

S 1 2

D 1 3

Output:

18

Тайлбар:

Эхний гурван үнээний хувьд HHG, HHJ, GGH, GGJ, JJH, JJG гэсэн 6 ялгаатай үүлдрүүдтэй байж болно. Харин 4 дэх үнээ H , J , G гурвын аль нь ч байж болох тул 6 * 3 = 18.

Орчуулсан : УБ 1-р сургууль Б.Мөнх-Оргил