本题和easy版本的唯一区别是：的数据范围不同！ 小红定义一个数组的权值为：数组所有元素乘积的因子数量。例如，[1,2,3]的权值为 4。 现在小红拿到了一个数组，她想求出数组中所有非空子序列的权值之和。你能帮帮她吗？由于答案过大，请对取模。 定义数组的子序列为：从左到右选择若干个元素（可以不连续）组成的数组，例如[1,2,3,2]的子序列有[2,2]等。因此，一个大小为的数组有恰好个子序列。

输入描述:

第一行输入一个正整数，代表数组大小。第二行输入个正整数，代表数组的元素。

输出描述:

一个整数，代表所有子序列的权值和。答案请对取模。