Mike is growing tired of searching for strings, and has instead become interested in breaking them apart! Given a string
The A
B
Z
For each subsequence, let HELLO
will have a score of
The total score of a string is equal to the sum of all the scores of its subsequences. To satisfy Mike's curiosity, you want to determine all the possible total scores for a given string.
Constraints
A
...Z
.
Subtask 1 [10%]
Subtask 2 [10%]
A
and B
.
Subtask 3 [30%]
Subtask 4 [50%]
No additional constraints.
Input Specification
The first line contains one integer
The second line contains the string
Output Specification
On the first line, output a single integer
On the next
Sample Input 1
3
ADB
Sample Output 1
4
-15
-3
0
12
Explanation for Sample Output 1
There are five possible ways to break up the string into subsequences:
AD
B
The total score for the first arrangement is
AB
D
The total score for the second arrangement is
A
D
B
The total score for the third arrangement is
A
DB
The total score for the fourth arrangement is
ADB
The total score for the fifth arrangement is
Sample Input 2
3
AAC
Sample Output 2
2
-8
0
Explanation for Sample Output 2
One way to achieve a total score of
A
AC
One way to achieve a total score of
AA
C
Sample Input 3
4
ABAB
Sample Output 3
4
-6
-3
0
3
Sample Input 4
4
JHVM
Sample Output 4
9
-489
-420
-384
-105
-69
0
36
315
351
Comments