#include <iostream>
#include <string>
 
using namespace std;
 
int numDistinct(string S, string T) {
	//corner cases
	if (!S.size() || !T.size() || S.size() < T.size()) return 0;
 
	//state counter array
	int* ct = new int[T.size()]();
	ct[0] = 1;
	int ret = 0;
	for (int i = 0; i<S.size(); i++)
		for (int j = T.size() - 1; j >= 0; j--)
			if (S[i] == T[j])
				if (j == T.size() - 1) ret += ct[j];
				else ct[j + 1] += ct[j];
 
	return ret;
}
 
int main() {
	string S = "rabbbit";
	string T = "rabbit";
 
	int ret;
	ret = numDistinct(S, T);
 
	cout << ret;
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBudW1EaXN0aW5jdChzdHJpbmcgUywgc3RyaW5nIFQpIHsKCS8vY29ybmVyIGNhc2VzCglpZiAoIVMuc2l6ZSgpIHx8ICFULnNpemUoKSB8fCBTLnNpemUoKSA8IFQuc2l6ZSgpKSByZXR1cm4gMDsKCgkvL3N0YXRlIGNvdW50ZXIgYXJyYXkKCWludCogY3QgPSBuZXcgaW50W1Quc2l6ZSgpXSgpOwoJY3RbMF0gPSAxOwoJaW50IHJldCA9IDA7Cglmb3IgKGludCBpID0gMDsgaTxTLnNpemUoKTsgaSsrKQoJCWZvciAoaW50IGogPSBULnNpemUoKSAtIDE7IGogPj0gMDsgai0tKQoJCQlpZiAoU1tpXSA9PSBUW2pdKQoJCQkJaWYgKGogPT0gVC5zaXplKCkgLSAxKSByZXQgKz0gY3Rbal07CgkJCQllbHNlIGN0W2ogKyAxXSArPSBjdFtqXTsKCQoJcmV0dXJuIHJldDsKfQoKaW50IG1haW4oKSB7CglzdHJpbmcgUyA9ICJyYWJiYml0IjsKCXN0cmluZyBUID0gInJhYmJpdCI7CgoJaW50IHJldDsKCXJldCA9IG51bURpc3RpbmN0KFMsIFQpOwoKCWNvdXQgPDwgcmV0OwoKCXJldHVybiAwOwp9