Description

王乐妍的衣柜被掏空了,可是还没有给学妹萌满意的小裙子,因此她开始自己写代码设计格裙。

王乐妍有一个数组 $f$, 下标为 $0$ ~ $2^{n}-1$.

王乐妍会选出若干个$0$ ~ $2^{n}-1$ 的互不相同的元素来组成小裙子，假设第 $i$ 个元素为 $a_i$ 总共选取了 $m(m \geqslant 1)$ 个元素

王乐妍希望这个序列同时满足：$\forall 1 \leqslant i<m,a_i\ \&\ a_{i+1}=a_i$ 王乐妍称这样的序列是萌萌哒的

现在王乐妍想要知道，对于所有萌萌哒的序列， $\prod \limits ^m_{i=1} f_{a_i}$的和

由于这个值非常大，王乐妍只想知道齐对 $1e9+7$ 取模的结果。

Format

Input

第一行 一个数 $n$ 。接下来一行

一个长度为 $2 ^n$ 的仅包含 $0-9$ 的字符串。第 $i$ 个位置上的字符代表 $f_i$的值。

Output

一行一个数表示答案

Samples

1
99

99

2
1111

11

约定和数据范围

对于符号$\prod$,为$\pi$的大写形式,意为求积(连乘)

本题共$20$ 个测试点满足 $n=i+2$

对于前$17$ 个测试点，每个测试点 $3$ 分

第$18$ 个测试点， $16$ 分

第$19$ 个测试点， $16$ 分

第$20$ 个测试点， $17$ 分

请注意本题特殊的内存限制