Palindromic Permutation

Given a string s consisting of lowercase English letters, determine whether any permutation of s can form a palindrome.

A palindrome is a string that reads the same forwards and backwards. For a permutation of s to form a palindrome, at most one character can appear an odd number of times. This can be formulated as follows: \[ \text{At most one character } c \text{ satisfies } \#(c) \mod 2 \neq 0, \] where \(\#(c)\) denotes the frequency of character c in s.

Constraints: 1 ≤ |s| ≤ 1000.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output a single line: True if any permutation of s can form a palindrome, otherwise output False.

a

True