서로 다른 부분 수열의 개수

문자열 $S = S_1S_2\cdots S_N$이 있다. $0 \le k \le N$이고 $1 \le i_1 < i_2 < \cdots < i_k \le N$일 때 $S_{i_1}S_{i_2}\cdots S_{i_k}$로 만들 수 있는 모든 문자열을 $S$의 부분 수열이라고 한다. 길이가 0인 빈 문자열도 $S$의 부분 수열이다. 예를 들어 문자열 ioi의 서로 다른 부분 수열은 빈 문자열, i, o, ii, io, oi, ioi로 모두 7개다.

문자열 $S$가 주어질 때, $S$의 서로 다른 부분 수열의 개수를 구하시오.

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

각 테스트 케이스마다 주어진 문자열 $S$의 서로 다른 부분 수열의 개수를 한 줄에 하나씩 출력한다. 빈 문자열도 개수에 포함한다. 입력으로는 답이 항상 $10^{18}$ 이하인 문자열만 주어진다.