孤独（single.cpp/.in/.out）2s 888MB

题目描述

在你的帮助之下，小明解开了《最佳男主角》的谜题。在短短几天的时间里，小明的名声在整个学校中传播开来，而小明的助教工作也越来越顺利。

"小明！" "小明！" "小明！" ...... 这天，小明刚刚走进自己班级里面的教室，就被一堆女生包围住了。看到这些女生，小明顿时感慨万千。

"小明，我们可算见到你啦！" "是啊，你整天在图书馆里卷也就算了，现在也不通知我们一下，害得我们好找啊！" "就是啊，小明，你说说你，现在也太不把我们放在眼睛里了吧！" "你不知道我们有多担心你啊，我们都在网上找你了，但是我们不敢直接联系你，我们怕会惹来麻烦！" ...... 众女生叽叽喳喳的，她们在小明的耳边说个没完，小明感觉脑袋有点晕，他连忙打断众女生的话："大姐们，咱能别在这儿站着吗？我脑袋晕啊！"

众女生听到他的话之后，连忙让开。小明坐在了自己的座位上，然后盯着这些女生道："喂！你们这些女

生，你们不要再围着我转了行不行？"

听到小明的话，这些女生纷纷白了李小强一眼，四散而去了。

不知不觉，小明已经大四了。这四年里，小明同学在学习方面一骑绝尘，天下第一卷王的称号在年级上如雷贯耳，可他仍然未曾尝过恋爱的滋味。也就是说，小明同学，仍是一只孤独的单身狗。

聪明的小明同学可不会肤浅地止步于单身这一表面现象，他对此进行了深刻地思索：人类是有限的，因而人是可数的。人是可数的，那么每个人，都和一个正整数对应，小明把这个数称为那个人的幸运数。为了简单，小明假设世界上有 $n$ 个人，编号 $1\sim n$，一开始第 $i$ 个人的幸运数是 $i$ 。总有一些公因数，像红线一样，把有缘人的幸运数连接起来。然而，也总有一些人的幸运数是互质的，它们没有大于 $1$ 的公因数，代表着他们生来就没有缘分。想到这里，小明不经感慨自己的孤独，这份孤独愈来愈浓，小明再也忍受不了了，他大吼着要改变这一切。

他想，只要改变每个人对应的幸运数，本来没有缘分的两个人，也有可能产生新的缘分。由于每个人都是独一无二的个体，小明认为，即使在改变以后，第 $i$ 个人的幸运数变成了 $a_i$，$(a_1,\ldots,a_n)$ 也应该是 $(1,\ldots,n)$ 的一个排列。小明目前只想好了几个人的幸运数，但他害怕自己的选择会做无用功。所以他又双叒选择求助于你，他告诉了你他目前想好的 $a_i$，他想知道，在这基础上，有多少种可能的排列会使得自己做无用功，即有缘分的人依然有缘分，没缘分的人依然没缘分。

一句话题意：$(a_i)$ 是 $1\sim n$ 的一个排列，给定其中部分数字，求有多少种可能的排列使得

$$\gcd(i,j) = 1 \iff \gcd(a_i,a_j)=1,\forall 1\le i< j\le n $$

输入格式

第一行，一个整数 $n$，代表这个小明幻想的世界里人的数量。

第二行，$n$ 个整数 $a_1,\ldots,a_n$，用空格隔开，代表小明想好的部分人的幸运数。$a_i=0$ 代表小明还没想好第 $i$ 号人的幸运数。保证大于 $0$ 的 $a_i$ 在范围内且互不相同。

输出格式

一个整数，代表小明做了无用功的排列数目。由于结果可能很大，请 ${\tt MOD}\ 10^9+7$ 后输出。

样例输入1

4
0 0 0 0

样例输出1

4

样例解释1

有 $4$ 种可能的排列 $(1,2,3,4),(3,2,1,4),(1,4,3,2),(3,4,1,2)$ 满足条件。

样例输入2

5
0 0 1 2 0

样例输出2

2

样例解释2

有 $2$ 种可能的排列 $(3,4,1,2,5), (5,4,1,2,3)$ 满足条件。

数据范围

对于 $20\%$ 的数据，$n\le 10$。

对于 $70\%$ 的数据，$n\le 1000000$。

对于 $100\%$ 的数据，$n\le 30000000$。

对于 $10\%$ 的数据， $a_i=0$。