class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        
        ls=len(s)
        lt=len(t)
        
        d=[[0 for j in xrange(lt+1)] for i in xrange(ls+1)]
        
        for i in xrange(ls):
            d[i][0]=1
        
        
        for i in xrange(1,ls+1):
            for j in xrange(1,lt+1):
                if s[i-1]==t[j-1]:
                    d[i][j]=d[i-1][j-1]+d[i-1][j]
                else: 
                    d[i][j]=d[i-1][j]
        return d[ls][lt]