You are given a function . In other words, is a function that takes an integer between and inclusive and returns an integer between and inclusive. Your task is to count the number of functions such that and commute under composition: that is, holds for any . As this number could be large, print the answer modulo .
输入格式
The input consists of a single test case of the following format.
The first line consists of an integer between and , inclusive. The second line consists of positive integers . For each , represents the value of . It is guaranteed that .
