小红的子序列权值和（hard）
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

第一行输入一个正整数n，代表数组大小。
第二行输入n个正整数a_i，代表数组的元素。
1\leq n \leq 10^5
1\leq a_i \leq 3

输出描述:

一个整数，代表所有子序列的权值和。答案请对10^9+7取模。
示例1

输入

复制 
3
1 2 2

输出

复制 
15

说明

[1]的权值为 1。
[2]的权值为 2。
[2]的权值为 2。
[1,2]的权值为 2。
[1,2]的权值为 2。
[2,2]的权值为 3。
[1,2,2]的权值为 3。