この問題はABC307-B(racecar)の強化版です

問題文

英小文字からなる$N$個の文字列$S_1,S_2,\cdots,S_N$が与えられる。
$1$以上$N$以下の相異なる整数$i,j$であって$S_i$,$S_j$をこの順番で繋げたものが回文であるものの個数を答えなさい。

制約

• $2 \leq N \leq 10^5$
• $1 \leq |S_i| \leq 10^5$
• $\sum |S_i| \leq 2 \times 10^5$
• $N$は整数である
• $S_i$は英小文字のみからなる文字列

入力

入力は以下の形式で標準入力から与えられます

出力

もし回文を作れないのならば $0$ を出力してください

サンプル

4
go
run
dog
nurses

2

2
pon
juice

0