문제

채완이는 1학년 후배들이 유클리드 호제법을 배웠다는 소식을 듣고 지문에 최대공약수가 들어간 문제를 만들기로 했다.

오름차순으로 정렬된 길이가 인 수열 의 최대공약수가 1일 때 이를 K-채완 수열이라 한다.

의 최대공약수는 모든 의 공통된 약수인 자연수 중 가장 큰 수를 의미한다.

서로 다른 개의 자연수가 주어질 때 서로 다른 개를 선택하여 K-채완 수열을 만드는 경우의 수를 구해보자.

입력

첫째 줄에 , 가 주어진다.

둘째 줄에 이하인 자연수 개가 공백으로 구분되어 주어진다.

출력

K-채완 수열을 만드는 경우의 수를 로 나눈 나머지를 출력하라.

노트

첫 번째 예제에서 주어진 수는 모두 소수이고 따라서 어떠한 쌍을 골라도 서로소다. 그러므로 정답은 이다.