题目背景

广告：讨论区有猫猫桑的重磅消息 👀️ 灵感来源：$\verb|2028|$ 届高一碑林区统考新定义填空压轴题。看似加强版实则不然。

定义一个集合的 猫A运算 为集合所有元素的积。

特殊地，空集的 猫A运算 结果为 $0$。

题目描述

给出一个集合，求集合所有子集的 猫A运算 的和。

输入格式

第一行一个正整数 $n$，表示集合元素的数量；

第二行 $n$ 个用空格隔开的整数为集合的元素。

输出格式

一个数，这个集合所有子集的 猫A运算 之和。

由于结果可能很大，输出所求 猫A运算 之和对于 $10^9+7$ 取模的结果即可。

输入输出样例

7
5 2 5 0 8 0 4

4859

说明/提示

👀️ $n \leq 10^6$，集合元素在 $\verb|int|$ 范围。