gets
c0, *cs = gets.chomp.reverse.chars
cs << nil
hs = [{}]
cs.each_with_index {|c, i|
  h = hs.last.clone
  h[c0] = i
  c0 = c
  hs << h
}
hs = hs.reverse
rec = lambda do |i, d|
  if d == 0
    hs[i].size
  else
    hs[i].map {|k, v| rec[-v-1, d-1] }.reduce(0, :+)
  end
end
puts rec[0, 2]
