Palindromic Permutations

Given a string S, determine whether it is possible to rearrange its characters to form a palindrome. A palindrome is a string that reads the same forwards and backwards. According to the principle, a palindromic permutation exists if and only if at most one character appears an odd number of times. Mathematically, if the number of characters with odd occurrences is \(\leq 1\), then a palindromic permutation exists.

For instance, for the input aabb, a valid palindromic permutation can be formed (e.g. abba), so the answer is 1. Otherwise, if no palindromic arrangement is possible, output 0.

inputFormat

The input consists of a single line containing the string S. The string may be empty and can include any characters.

outputFormat

Output a single integer: print 1 if a palindromic permutation of S exists, otherwise print 0.## sample

aabb

1