A subsequence of a string S (or any kind of sequence, really) is simply a sequence consisting of zero or more characters from S in the same order as in S; for example, "ack", "", "bk", and "back" are all subsequences of "back", but "kb" and "bb" are not. A substring of S is a contiguous subsequence of zero or more characters of S; for example "ack", "ba", "" and "back" are substrings of "back", but "bk" is not. Given a string S of length N,

how many subsequences does it have?