问题描述

塔子哥最近迷上了一个字符串重排的游戏。游戏规则如下:给定一个由小写字母组成的字符串 $s$,通过重新排列 $s$ 中的字母,看看最多能组成多少个不同的回文字符串。回文字符串是指一个字符串正着读和反着读完全一样,例如"level"和"noon"都是回文字符串,而"code"不是。

请你帮塔子哥写一个程序,计算给定字符串 $s$ 经过重排后最多能组成的不同回文字符串数量。

输入格式

输入一行,包含一个由小写字母组成的字符串 $s$,表示塔子哥手中的初始字符串。

输出格式

输出一个整数,表示字符串 $s$ 经过重排后最多能组成的不同回文字符串数量。如果无法组成任何回文字符串,则输出 $0$。

样例输入

aabb

样例输出

2

评测数据与规模

• $1 \leq |s| \leq 1000$
• 字符串 $s$ 只包含小写字母