Scrambled Palindrome

Given a string s, determine whether it can be rearranged to form a palindrome. A palindrome is a string that reads the same backward as forward. In other words, check if s is a scrambled palindrome.

A necessary and sufficient condition for a string to be rearranged into a palindrome is that at most one character appears an odd number of times. Formally, let \( f(c) \) denote the frequency of character \( c \) in s. Then, s can form a palindrome if and only if

[ \sum_{c} [f(c) \bmod 2 \neq 0] \leq 1 ]

For example, the string "carrace" can be rearranged into "racecar", which is a palindrome.

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 10⁶), which is composed of ASCII characters.

outputFormat

Output a single line: True if the string can be rearranged to form a palindrome, or False otherwise.

carrace

True