Rearranged Palindrome

Given a string s containing only lowercase letters, determine whether it is possible to rearrange the characters of s to form a palindrome.

A palindrome is a string that reads the same backward as forward. 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. Mathematically, if we let \( f(c) \) be the frequency of character c in s, then the string can form a palindrome if and only if:

$$\sum_{c}\mathbf{1}_{\{f(c)\;\text{is odd}\}} \le 1$$

Write a program that reads a string from standard input and prints True if the string can be rearranged into a palindrome, and False otherwise.

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 10⁵), which is composed of lowercase English letters.

outputFormat

Output True if the string can be rearranged to form a palindrome; otherwise, output False.

carrace

True