题目描述

有一种用摸彩方式完成排序的算法：每次从序列中随机挑选两个位置（不一定相邻），检查这两个数是否构成逆序（左大右小称之为逆序），若是则交换这两个数，循环反复直到序列完全升序为止。

给定一个只由 $0$ 与 $1$ 构成序列，请问使用上述策略，期望情况下需要摸彩多少次才能完成排序？

输入格式

• 若干 01 字符组成的一个序列

输出格式

设答案为一个有理数 $P/Q$，且 $P$ 和 $Q$ 互素，则应该输出一个整数，具体数值为

其中 $Q'$ 满足 $Q'Q\equiv 1\pmod {1,000,000,007}$

010

3

样例解释 1

1/3的概率选中最后两个数，所以期望为3步

000111

0

样例解释 2

不需要摸彩就能完成排序

数据范围

记 $n$ 表示输入序列的长度：

• $30\%$ 的数据，$1\leq n\leq 20$
• $60\%$ 的数据，$1\leq n\leq 5000$
• $100\%$ 的数据，$1\leq n\leq 300,000$