关灯

题目描述 有𝑛𝑛盏灯排成了一排，一开始有些灯是开的，有些灯是关的。我们用01串表示，其 中 1 表示开着，0 表示关着。

你要从第𝑝𝑝盏灯开始，每次做如下操作：

• 朝左或者朝右走一步，也就是从𝑥𝑥走到𝑥𝑥 − 1或𝑥𝑥 + 1位置，要求走到的位置 还是在1到𝑛𝑛之间。

• 改变当前位置灯的状态（开的变成关的，关的变成开的）。

对于𝑝𝑝 = 1,2, … , 𝑛𝑛，求出把所有灯都关闭的最小步数。令𝑎𝑎𝑎𝑎𝑠𝑠𝑖𝑖 表示起点是𝑖𝑖的最小步 数，为了减小输出的大小，输出(∑𝑛𝑛𝑖𝑖=1 𝑖𝑖 × 𝑎𝑎𝑎𝑎𝑠𝑠𝑖𝑖 ) mod 109 + 7。

输入格式 第一行，输入一个整数𝑛𝑛。

接下来一行，输入一个长度为𝑛𝑛的01串。

输出格式 输出一个数，表示答案。

样例输入 1 8 01010101

样例输出 1 432

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点1满足𝑛𝑛 ≤ 8。

测试点2,3满足𝑛𝑛 ≤ 15。

测试点4,5满足𝑛𝑛 ≤ 1000。

测试点6,7满足𝑛𝑛 ≤ 105 。 对于所有数据，满足1 ≤ 𝑛𝑛 ≤ 5 × 106 。