思路:数学题 or 数位dp

step1:转换题意

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

题目内容

在一个由字符 'A' 和 'B' 构成的竞赛题序列中，定义序列的难度分为其中 'A' 的出现次数。现在，给出一个特定的序列 $s$，请你计算所有长度与 $s$ 相同的、仅由 'A' 和 'B' 组成的序列中，字典序不小于 $s$ 的序列的难度分之和。由于答案可能很大，请输出结果对 $10^9+7$ 取模后的值。

约束条件：

• 字符串的长度 $n$ 满足 $2 \le n \le 10^5$。
• 字符串 $s$ 仅由字符 'A' 和 'B' 构成。

输入描述

第一行包含一个整数 $n$，表示字符串的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，字符串中仅包含字符 'A' 和 'B'。

输出描述

输出一个整数，表示所有字典序不小于 $s$ 的、长度同为 $n$ 且仅由 'A' 和 'B' 组成的字符串的难度分之和，对 $10^9+7$ 取模。

样例1

输入

2
BB

输出

4

说明

序列为 BB。由于字符顺序 $B < R$，BB 是长度为 $2$ 的字典序最小的序列，因此所有 $2^2=4$ 个序列的字典序均不小于它。这 $4$ 个序列为 BB（含 $0$ 个 R）、BR（含 $1$ 个 R）、RB（含 $1$ 个 R）、RR（含 $2$ 个 R）。难度分之和为 $0+1+1+2=4$。

样例2

输入

2
BR

输出

4

说明

序列为 BR。字典序不小于 BR 的序列有 BR、RB、RR。对应的难度分分别为 $1$、$1$、$2$，总和为 $1+1+2=4$。

样例3

输入

2
RB

输出

3

说明

序列为 RB。字典序不小于 RB 的序列有 RB、RR。对应的难度分分别为 $1$、$2$，总和为 $1+2=3$。

样例4

输入

2
RR

输出

2

说明

序列为 RR，是字典序最大的序列。不小于它的序列仅为其自身，包含 $2$ 个 R，难度分之和为 $2$。