PIPI想跟你玩一个游戏。

规定一个区间的价值为这个区间中所有数按位与起来的值与这个区间所有数按位或起来的值的乘积。

例如3个数2,3,6。它们and起来的值为2，or起来的值为7，这个区间对答案的贡献为2*7=14。

现在PIPI有一个n个数的序列，它想知道所有n*(n+1)/2个子区间的贡献的和对1000000007取模后的结果是多少。

例如当这个序列为{3,4,5}时，那么区间[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]的贡献分别为9,0,0,16,20,25。

第一行一个数n(1<=n<=100000)。
接下来一行n个数ai，表示这n个数(0<=ai<=10^9)。

一行表示答案。