小w的互质集

题号：NC25114
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

doge有一个集合A，A中有n个互不相同的元素且每个元素均为 $2$ 到 $1000$ 范围内的正整数。

他要求小w从A中选出一个集合B，使得 $B\subseteq A$ 且 $\forall a,b\in B,gcd(a,b)=1$ ,a和b不是同一个元素。

也就是说要求小w选出A的一个子集B,B中元素两两互质。

集合B可以为空集，我们认为空集也是一个符合条件的互质集。

本来doge想让小w回答最多能选出多少种不同的B集合。

但是doge觉得这个问题可能太简单了，他就想办法刁难小w，于是他说：如果我的A集合是不断变化的，你还能求出互质集的数量么？

当doge说1的时候，表示他现在要将一个数字x加入到集合A当中，数字x的范围也在2到1000，并且在操作前，A集合没有x。

当doge说2的时候，表示他现在要将一个数字x从集合A当中删除，数字x的范围也在2到1000，并且在操作前A集合中一定存在x。

当doge说3的时候，表示问小w最多能选出多少种不同的B集合，请你输出答案对 $10^{9}+7$ 取模后的结果。

当且仅当两个集合中含有至少一个元素不同时，我们认为它们是不一样的集合。

也就是说对于两个集合A，B

当且仅当 $\exists a\in A,a\notin B$ 或者 $\exists a\in B,a\notin A$ 时， $A\neq B$

输入描述:

第一行是一个正整数n $(0\leqslant n\leqslant 999)$ 。且当n=0时，表示A集合为空集。

若n不为0，则接下来一行n个互不相同的正整数ai $(2\leqslant a_{i}\leqslant 1000)$ 。

接下来输入一个正整数m $(1\leqslant m\leqslant 1000)$ ，表示操作的数量。

接下来m行，每行先输入一个正整数Q，表示操作类型。

如果Q=1，则还需输入一个正整数x，表示需要添加的数字。

如果Q=2，则还需输入一个正整数x，表示删除的数字。

如果Q=3，请你帮助小w求出当前能从A中选出多少个符合条件的B集合，并输出答案对取 $10^{9}+7$ 模后的结果。

输入数据保证至少进行了一次查询操作

输出描述:

对于每一个Q=3，输出答案对取模后的结果。

示例1

输入

复制

输出

复制

说明

一开始A集合为，此时查询答案为1，即B集合也是
加入2后，A集合为{2}，答案为2，B可为、{2}
加入3后，A集合为{2,3}，答案为4，B可为、{2}、{3}、{2,3}
加入6后，A集合为{2,3,6}，答案为5，B集合可为、{2}、{3}、{6}、{2,3}
加入4后，A集合为{2,3,4,6}答案为7，B集合可为、{2}、{3}、{4}、{6}、{2,3}、{3,4}
移除6后，A集合为{2,3,4}，答案为6，B集合可为、{2}、{3}、{4}、{2,3}、{3,4}
加入8后，A集合为{2,3,4,8}，答案为8，B集合可为、{2}、{3}、{4}、{8}、{2,3}、{3,4}、{3,8}

示例2

输入

复制

输出

复制

3
5

说明

431是一个质数
862=431*2
所以一上来答案为3，B可为、{431}、{862}
加入2后答案为5，B可为、{2}、{431}、{862}、{431，2}

示例3

输入

复制

10
2 3 5 7 11 13 17 19 23 29
1
3

输出

复制

说明

10个质数都可以选或者不选，最终答案为=1024

示例4

输入

复制

9
2 4 8 16 32 64 128 256 512
1
3

输出

复制

说明

9个数均为2的幂，算上不选一共10种合法的情况。