9999025 - 小 G 的字符串

小 G 有一个长度为 n 的字符串 s，字符串由 0 和 1 组成。 小 G 有一种针对字符串的变换方法，对一个字符串 s 进行一次变换的具体规 则如下：

1. 记 s ′ 为变换后得到的字符串，若 s 的长度为 p，则 s ′ 的长度为 p − 1。
2. 若 si = si+1，那么 s ′ i = si。
3. 若 si ̸= si+1，那么 s ′ i 有 1 2 的概率为 si，有 1 2 的概率为 si+1。 接下来小 G 要对该字符串重复做以上变换 n − 1 次，最后小 G 会得到一个长 度为 1 的字符串，现在小 G 想知道最终这个长度为 1 的字符串是 0 的概率。请你 输出这个值模 109 + 7 的结果。

第一行一个整数 n，表示字符串的长度。 接下来一行一个长度为 n 的由 0 和 1 组成的字符串 s。

输出共一行一个整数，表示最终字符串变成 0 的概率模 109 + 7 的结果。