Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Check the string

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA has a string consisting of some number of lowercase English letters 'a'. He gives it to his friend B who appends some number of letters 'b' to the end of this string. Since both A and B like the characters 'a' and 'b', they have made sure that at this point, at least one 'a' and one 'b' exist in the string.

B now gives this string to C and he appends some number of letters 'c' to the end of the string. However, since C is a good friend of A and B, the number of letters 'c' he appends is equal to the number of 'a' or to the number of 'b' in the string. It is also possible that the number of letters 'c' equals both to the number of letters 'a' and to the number of letters 'b' at the same time.

You have a string in your hands, and you want to check if it is possible to obtain the string in this way or not. If it is possible to obtain the string, print "YES", otherwise print "NO" (without the quotes).

Input

The first and only line consists of a string $$$S$$$ ($$$ 1 \le |S| \le 5\,000 $$$). It is guaranteed that the string will only consist of the lowercase English letters 'a', 'b', 'c'.

Output

Print "YES" or "NO", according to the condition.

Examples

Input

aaabccc

Output

YES

Input

bbacc

Output

NO

Input

aabc

Output

YES

Note

Consider first example: the number of 'c' is equal to the number of 'a'.

Consider second example: although the number of 'c' is equal to the number of the 'b', the order is not correct.

Consider third example: the number of 'c' is equal to the number of 'b'.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/19/2018 15:49:11 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|