[COCI2011-2012#5] RAZBIBRIGA

题目描述

四个长度相同的单词可以拼成一个正方形,如下图,`"HLAD","NIVA","HSIN","DEDA"` 拼成了一个 $4\times 4$ 的正方形。 ![](https://cdn.luogu.com.cn/upload/image_hosting/7i3lhwgv.png) 现在给你 $N$ 个等长的单词,求这些单词的子集可以拼成多少个不同的正方形,输出方案数。 注意,**同一方格内不能有重复的单词**,如果两个单词至少有一个字符不同,那这两个单词就是不同的。

输入输出格式

输入格式


第一行,一个整数 $N$,表示单词数。 接着 $N$ 行,每行一个单词,由大写字母组成,如题所示。

输出格式


一行,一个整数,表示方案数。 方案数可能很大,你需要开 `long long` 或 `int64`。

输入输出样例

输入样例 #1

4
NIVA
HLAD
HSIN
DEDA

输出样例 #1

2

输入样例 #2

6
BAKA
BARA
BALC
CALC
ARHC
BLIC

输出样例 #2

8

说明

$4\le N\le 10^{5}$。 每个单词至多有 $10$ 个字符。 单词由大写字母构成。 题目译自 [COCI 2011/2012 #5 T4](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。