문제

크기가 인 수열 에 대하여 다음 조건을 만족하는 크기의 행렬 의 개수를 구하시오.

• 이고 인 모든 정수 , 에 대하여 이다.
• 인 모든 정수 에 대하여 이다.
• 이고 인 모든 정수 , 에 대하여 이다.

입력

첫 번째 줄에 행렬의 크기를 나타내는 정수 , 이 공백을 사이에 두고 차례로 주어진다.

두 번째 줄에 의 원소 이 공백을 사이에 두고 차례로 주어진다. 모든 는 정수

출력

문제의 조건을 만족하는 행렬 의 개수를 으로 나눈 나머지를 출력하시오.