# #P17C. Balance

# Balance

## Description

Nick likes strings very much, he likes to rotate them, sort them, rearrange characters within a string... Once he wrote a random string of characters a, b, c on a piece of paper and began to perform the following operations:

- to take two adjacent characters and replace the second character with the first one,
- to take two adjacent characters and replace the first character with the second one

To understand these actions better, let's take a look at a string «abc». All of the following strings can be obtained by performing one of the described operations on «abc»: «bbc», «abb», «acc». Let's denote the frequency of a character for each of the characters a, b and c as the number of occurrences of this character in the string. For example, for string «abc»: |*a*| = 1, |*b*| = 1, |*c*| = 1, and for string «bbc»: |*a*| = 0, |*b*| = 2, |*c*| = 1.

While performing the described operations, Nick sometimes got balanced strings. Let's say that a string is balanced, if the frequencies of each character differ by at most 1. That is - 1 ≤ |*a*| - |*b*| ≤ 1, - 1 ≤ |*a*| - |*c*| ≤ 1 и - 1 ≤ |*b*| - |*c*| ≤ 1.

Would you help Nick find the number of different balanced strings that can be obtained by performing the operations described above, perhaps multiple times, on the given string *s*. This number should be calculated modulo 51123987.

The first line contains integer *n* (1 ≤ *n* ≤ 150) — the length of the given string *s*. Next line contains the given string *s*. The initial string can be balanced as well, in this case it should be counted too. The given string *s* consists only of characters a, b and c.

Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string *s*, modulo 51123987.

## Input

The first line contains integer *n* (1 ≤ *n* ≤ 150) — the length of the given string *s*. Next line contains the given string *s*. The initial string can be balanced as well, in this case it should be counted too. The given string *s* consists only of characters a, b and c.

## Output

Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string *s*, modulo 51123987.

## Samples

```
4
abca
```

```
7
```

```
4
abbc
```

```
3
```

```
2
ab
```

```
1
```

## Note

In the first sample it is possible to get 51 different strings through the described operations, but only 7 of them are balanced: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». In the second sample: «abbc», «aabc», «abcc». In the third sample there is only one balanced string — «ab» itself.