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

你要从第 p 盏灯开始，每次做如下操作：
• 朝左或者朝右走一步，也就是从 x 走到 x−1或 x+1位置，要求走到的位置还是在 1 到 n 之间。
• 改变当前位置灯的状态（开的变成关的，关的变成开的）。

对于 p=1,2, … ,n ，求出把所有灯都关闭的最小步数。令 ans[i] 表示起点是 i 的最小步数，为了减小输出的大小，输出 (1*ans[1]+2*ans[2]+...+n*ans[n]) mod 10^9+7 。

第一行，输入一个整数 n 。
接下来一行，输入一个长度为 n 的01串。

输出一个数，表示答案。

8
01010101

432

数据规模
共 10 个测试点。
测试点 1 满足 n≤8 。
测试点 2,3 满足 n≤15 。
测试点 4,5 满足 n≤1000 。
测试点 6,7 满足 n≤10^5 。
对于所有数据，满足 1≤n≤5×10^6 。