题目内容

小红是一个程序员，他最近在处理一些字符串相关的任务。他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果。另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符通常表示“错误”的结果。

为了解决他的任务，小红定义了字符串的权值为字符串中 R 字符的出现次数。例如，对于字符串 BBRBRB，它的权值为 $2$，因为其中有 $2$ 个 R 字符。

现在，小红面临一个问题，他有一个长度为 $n$ 的字符串 $s$，它仅由 R 和 B 组成。他想知道，长度为 $n$ 的仅由 R 和 B 组成的字符串中，字典序不小于 $s$ 的字符串的权值之和是多少？因此，他需要编写一个程序来解决这个问题。

由于答案可能太大，需要对 $10^9+7$ 取模后再输出。

输入描述

输入第一行为一个整数 $n$ ，表示字符串的长度。

输入第二行为一个长度为 $n$ 的字符串 $s$ ，字符串中元素组成仅为 R 和 B 。

$2\le n \le 10^5$

输出描述

输出一个整数，代表长度为 $n$ 的、字典序不小于 $s$ 的字符串权值之和。

样例

输入

3
RBR

输出

7

样例解释

共有 $3$ 个字符串符合要求： RBR 的权值为 $2$ 。

RRB 的权值为 $2$ 。

RRR 的权值为 $3$ 。

思路:数学题 or 数位dp

step1:转换题意

将$R$ 看作1,$B$看作0.原字符串变成一个二进制数$x$.那么题目意思转化为：输出值域$[x,2^{|x|}-1]$ 内每个数的二进制位1的个数的总和。