옷의 이름과 종류가 주어진다.

하루에 입을 옷을 고를 때, 같은 종류의 옷은 최대 하나만 고를 수 있다. 아무것도 고르지 않는 경우는 제외한다.

만들 수 있는 서로 다른 옷 조합의 수를 구하시오.

입력

첫째 줄에 옷의 개수 \(n\)이 주어진다.

이후 \(n\)개의 줄에 옷의 이름과 옷의 종류가 공백으로 구분되어 주어진다.

출력

만들 수 있는 서로 다른 옷 조합의 수를 출력한다.

제한 사항

• \(1 \le n \le 30\)
• 옷의 이름과 종류는 알파벳 소문자로 이루어져 있으며 길이는 \(1\) 이상 \(20\) 이하이다.
• 같은 이름의 옷은 두 번 이상 주어지지 않는다.
• 정답은 \(2,147,483,647\) 이하이다.

예제 입력 1

3
cap head
sunglasses face
turban head

예제 출력 1

5

예제 설명 1

head 종류에서 고를 수 있는 방법은 cap, turban, 고르지 않음까지 3가지이다.

face 종류에서 고를 수 있는 방법은 sunglasses, 고르지 않음까지 2가지이다.

따라서 전체 경우는 \(3 \times 2 = 6\)가지이고, 아무것도 고르지 않는 1가지를 제외하면 답은 \(5\)이다.