Определить, сколько различных палиндромов можно получить, переставляя буквы в заданном слове

{$APPTYPE CONSOLE}
{$O-}
uses
  SysUtils;
 
const
  infile = 'D.in';
  outfile = 'D.out';
  maxn = 26;
  max = 1000000000;
 
var
  a: array [1 .. maxn] of longint;
  c: array [1 .. 100] of longint;
  s: int64;
  i, j, y, k, kol: longint;
  str: string;
 
begin
  reset(input, infile);
  rewrite(output, outfile);
  readln(str);
  for i := 1 to length(str) do
    inc(a[ord(str[i]) - ord('a') + 1]);
 
  kol := 0;
  k := 0;
  for i := 1 to maxn do
  begin
    if a[i] mod 2 = 1 then
      inc(kol);
    a[i] := a[i] div 2;
    k := k + a[i];
  end;
  if kol < 2 then begin
    kol := k - 1;
    for i := 2 to k do
      c[i - 1] := i;
    for i := 1 to maxn do begin
      for j := 2 to a[i] do begin
        y := 1;
        while c[y] mod j <> 0 do
          inc(y);
        c[y] := c[y] div j;
      end;
    end;
    s := 1;
    for i := 1 to kol do
      if c[i] > 0 then
        s := (s * c[i]) mod max;
    writeln(s);
  end else
    writeln(0);
  close(input);
  close(output);
 
end.