Problem J: J 清洁能源
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$63$ |
正确数量 |
$26$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
化石能源是全球消耗的最主要能源，2006年全球消耗的能源中化石能源占比高达87.9%，我国的比例高达93.8%。但随着人类的不断开采，化石能源的枯竭是不可避免的，大部分化石能源本世纪将被开采殆尽。从另一方面看，由于化石能源的使用过程中会新增大量温室气体CO2，同时可能产生一些有污染的烟气，威胁全球生态。因而，开发更清洁的可再生能源是今后发展的方向。
现在，科研人员研制出了一种全新的清洁的可再生能源，这种可再生能源具有非常神奇的性质。科研人员基于该可再生能源发明了一种发电装置，该装置有n 个能源槽位，第i个能源槽位中放入了i份新能源。该发电装置的能源槽位的位置可以进行随意交换，但是，对于其中任意一对能源槽位，只有满足当且仅当这两个能源槽位的位置编号互质且其中的新能源量互质，这种情况下发电装置才能得到最大的发电功率。
现在，发电装置的能源槽位已经被进行了一些交换，而其中一些能源槽位中的新能源量已知，科研人员想要知道有多少种方案可以得到最大的发电功率，结果对1e9+7取模。
输入包含多组数据，第一行输入数据组数T
每组数据的输入如下：
第一行一个正整数 n；第二行 n 个数 a1,a2,.,an；若 ai=0 则这个槽位的新能源量未知，否则代表该槽位的新能源量。
满足条件的方案个数，对1e9+7取模。