14335번 - 서로 다른 부분 수열의 개수

문제

어떤 문자열 S = S₁S₂...S_N이 있을때, S_i1S_i2...S_ik (0 ≤ k ≤ N, 1 ≤ i₁ < i₂ < ... < i_k ≤ N)을 만족하는 모든 문자열을 S의 부분 수열이라한다. 길이가 0인 빈 문자열도 S의 부분 수열이다. 문자열 ioi의 서로 다른 부분 수열은 빈 문자열, i, o, ii, io, oi, ioi로 총 7개가 있다.

문자열 S가 주어진다. 이 문자열의 서로 다른 부분 수열의 개수를 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 10,000)가 주어진다. 둘째 줄부터 한 줄에 하나씩 문자열 S가 주어진다. S는 영어 알파벳 대문자와 소문자로, 0부터 9까지의 숫자만 이루어져 있고, 길이는 1,000 이하이다.

출력

각각의 테스트 케이스마다 입력으로 주어진 문자열 S의 서로 다른 부분 수열의 개수를 출력한다. 항상 개수가 10¹⁸ 이하인 문자열만 입력으로 주어진다.

제한

힌트