题目描述

这天，小 A 遇到了一道他最讨厌的排列计数题：求有多少个长度为 $n$ 的排列 $p$ 满足 $\gcd(i,j)=1\Leftrightarrow\gcd(p_i,p_j)=1 (1\le i<j\le n)$。

tzc_wk 看罢，觉得题目太简单了，于是添加了一些限制 $(i,v)$ 表示钦定 $p_i=v$。

请你求满足上述所有条件的 $n$ 阶排列个数，对 $998244353$ 取模。

输入格式

第一行一个整数 $n$，表示排列长度。

第二行 $n$ 个整数 $p_i$。若 $p_i = −1$ 则表示该位没有限制；否则 $p_i$ 被钦定等于输入值。

输出格式

一行一个整数，表示答案。

样例

5
-1 -1 -1 -1 1

4

排列 $[3, 2, 5, 4, 1]$，$[3, 4, 5, 2, 1]$，$[5, 2, 3, 4, 1]$，$[5, 4, 3, 2, 1]$ 满足题意。

见附加文件下的 permutation2.in

见附加文件下的 permutation2.ans

该样例满足 Subtask 2 的限制。

见附加文件下的 permutation3.in

见附加文件下的 permutation3.ans

该样例满足 Subtask 3 的限制。

见附加文件下的 permutation4.in

见附加文件下的 permutation4.ans

该样例满足 Subtask 4 的限制。

数据范围

对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$-1\le p_i\le n$，保证若 $x\not=y$ 且 $p_x,p_y\not=1$，则 $p_x\not=p_y$。