题目描述

牛牛有一个长度为 $n$ 的 $Link-Cut$ 数组，每个节点有Link（状态为'$1$'）和Cut（状态为'$0$'）两种状态。 数组中任意一对处于Link状态的无序点对 $(u,v)$（$(u,v)$ 与 $(v,u)$ 视为同一对）会产生能量 $\text{dis}(u,v)$（$\text{dis}(u,v)$ 为数组中 $u$ 到 $v$ 的距离）。 整个数组的Link能量为所有Link状态点对的能量之和，最终结果需对 $10^9+7$ 取模。

输入格式

• 第一行：正整数 $n$（$1 \leq n \leq 10^5$）
• 第二行：长度为 $n$ 的 $01$ 串，表示每个节点的初始状态（'$1$'为Link，'$0$'为Cut）

输出格式

一行，输出Link能量对 $10^9+7$ 取模后的结果

样例 1

样例输入 1

3
101

样例输出 1

2

样例 2

样例输入 2

5
00110

样例输出 2

1

样例 3

样例输入 3

6
000010

样例输出 3

0