Given a sequence , a good subsequence of is defined as a subsequence, that is not necessarily contiguous, where adjacent elements in the subsequence are not coprime.
Find the maximum length of a good subsequence of . Also, determine the number of good subsequences of length , modulo .
输入格式
The input is given in the following format:
All input values are integers.
输出格式
Output 2 lines. On the first line, output . On the second line, output the number of good subsequences of length of , modulo .
