단순 사이클의 개수

그래프 $G$에서 길이가 $L \ge 3$인 단순 사이클은 정점 순열 $(v_0, v_1, \dots, v_{L-1})$이다. $v_0, v_1, \dots, v_{L-1}$은 서로 모두 다르고, 모든 $0 \le i \le L-1$에 대해 $v_i$와 $v_{(i+1) \bmod L}$을 잇는 간선이 $G$에 있다.

두 단순 사이클 $X$와 $Y$는, $X$를 회전하거나 뒤집은 다음 회전해서 $Y$를 만들 수 있으면 같은 사이클이다. 예를 들어 $(1, 2, 3, 4)$, $(2, 3, 4, 1)$, $(3, 2, 1, 4)$는 모두 같은 사이클이다.

트리 두 개를 이어 붙여 그래프를 만든다. 두 트리는 모두 정점이 $N$개이고, 정점에는 0번부터 $N-1$번까지 번호가 매겨져 있다. 먼저 0부터 $N-1$까지의 수로 이루어진 순열 $P$를 하나 만든다. 그 다음 모든 $0 \le i \le N-1$에 대해 첫 번째 트리의 $i$번 정점과 두 번째 트리의 $P[i]$번 정점을 간선으로 잇는다.

이렇게 만든 그래프에서 첫 번째 트리에 있던 $i$번 정점은 $A_i$로, 두 번째 트리에 있던 $i$번 정점은 $B_i$로 나타낸다.

$P$를 어떻게 고르는지에 따라 길이가 $K$인 단순 사이클의 개수가 달라진다. 두 트리와 $K$가 주어지면, 길이가 $K$인 단순 사이클의 개수가 가장 많아지도록 $P$를 골랐을 때 그 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $K$가 주어진다. ($1 \le N \le 9$, $3 \le K \le 7$)

둘째 줄부터 $N$개 줄에 첫 번째 트리의 정보가, 이어지는 $N$개 줄에 두 번째 트리의 정보가 주어진다. 트리는 인접 행렬로 주어진다. 각 줄은 길이가 $N$인 문자열이고, $i$번째 줄의 $j$번째 문자가 'X'이면 $i$번 정점과 $j$번 정점을 잇는 간선이 있다는 뜻이고, '-'이면 없다는 뜻이다.

첫째 줄에 주어진 두 트리를 이어 붙여 만들 수 있는 그래프에서 길이가 $K$인 단순 사이클 개수의 최댓값을 출력한다.