앞에서 읽어도 뒤에서 읽어도 같은 문자열을 팰린드롬이라고 한다.

팰린드롬 문자열 \(N\)개가 주어진다. 팰린드롬은 첫 문자와 마지막 문자가 같으므로, 이 문자열들을 어떤 순서로 나열하여 끝말잇기를 완성하려면 모든 문자열의 첫 문자가 같아야 한다.

주어진 문자열을 모두 한 번씩 사용하여 끝말잇기를 만들 수 있는지 판단하여라.

입력

첫째 줄에 문자열의 개수 \(N\)이 주어진다.

둘째 줄에 알파벳 소문자로 이루어진 팰린드롬 문자열 \(N\)개가 공백으로 구분되어 주어진다.

• \(1\le N\le 100\)
• 각 문자열의 길이는 \(1\) 이상 \(100\) 이하이다.

출력

모든 문자열을 사용하여 끝말잇기를 만들 수 있으면 1, 그렇지 않으면 0을 출력한다.

예제 입력 1

4
aa aba acca adddda

예제 출력 1

1

예제 입력 2

3
level radar noon

예제 출력 2

0