塔子哥是一位对数学问题十分着迷的年轻人。最近,他参加了一场数学竞赛,其中有一道问题要求他计算一个大小为 n 的集合中元素数量大于 1 的子集,满足子集内的元素两两之间互为倍数关系的个数。但是在考场的时候塔子哥并没有想出来如何解决,考试完了回来以后他为了这个题废寝忘食,一直在思考这个问题,也没有很大的进展,作为他最好的朋友的你能不能帮他想一想这个题目要如何解决?
由于子集数量可能过大,请对 109+7 取模。
第一行输入一个正整数 n ,代表集合大小。
第二行输入 n 个正整数 ai ,代表集合的元素。
1≤n≤105
1≤ai≤106
一个整数,代表满足题意的子集数量对 对 109+7 取模的值。
输入
5
1 2 3 4 5
输出
6
样例解释
共有6个合法的子集:
{1,2},{1,3},{1,4},{1,5},{1,2,4},{2,4}
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.