=begin
 
466 デフォルトの名無しさん 2020/05/09(土) 20:03:47.46 ID:slqshlLL
    お題
    文字列Sが与えらえる。Sの部分列に"odai"は何個あるか？
 
    [1] odadai => 3
    部分列は以下の3通り
    oda__i
    od__ai
    o__dai
 
    [2] odaiodai => 5
 
    [3] ooooddddaaaaiiii => 256
 
    [4] daioadiao => 0 
 
=end
 
$ans = 0
 
def combi( pa, i = 0, n = -1 )
	pa[i].each{|pn|
		next	if pn <= n
		if i < pa.length - 1
			combi( pa, i+1, pn )
			next
		end
		$ans += 1
	}
end
 
def solve( pat, str )
	pa = []
	i = 0
	n = 0
	pat.each_char{|ch|
		pn = []
		while( n = str.index(ch,n) )
			pn << n
			n += 1
		end
		break	if pn.empty?	# 解無し
		pa << pn
		i += 1
		n = pn.min
	}
	$ans = 0
	combi( pa )	if pa.size == pat.size
	puts $ans
end
 
	pat = "odai"
	solve( pat, "odadai" )				#=> 3
	solve( pat, "odaiodai" )			#=> 5
	solve( pat, "ooooddddaaaaiiii" )	#=> 256
	solve( pat, "daioadiao" )			#=> 0
 
=begin
 
	o d a d a i
o	1 0 0 0 0 0		0
d	0 1 0 1 0 0		1,3
a	0 0 1 0 1 0		2,4
i	0 0 0 0 0 1		5
	0 1 2 3 4 5
[[0], [1, 3], [2, 4], [5]]
 
	o d a i o d a i
o	1 0 0 0 1 0 0 0
d	0 1 0 0 0 1 0 0
a	0 0 1 0 0 0 1 0
i	0 0 0 1 0 0 0 1
[[0, 4], [1, 5], [2, 6], [3, 7]]
 
ooooddddaaaaiiii
[[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]]
 
daioadiao
[[3, 8], [5], [4, 7], [6]]
[[3, 8], [5], [7]]		# 枝刈り 1passで解無し確定
 
=end
 

PWJlZ2luCgo0NjYg44OH44OV44Kp44Or44OI44Gu5ZCN54Sh44GX44GV44KTIDIwMjAvMDUvMDko5ZyfKSAyMDowMzo0Ny40NiBJRDpzbHFzaGxMTAogICAg44GK6aGMCiAgICDmloflrZfliJdT44GM5LiO44GI44KJ44GI44KL44CCU+OBrumDqOWIhuWIl+OBqyJvZGFpIuOBr+S9leWAi+OBguOCi+OBi++8nwoKICAgIFsxXSBvZGFkYWkgPT4gMwogICAg6YOo5YiG5YiX44Gv5Lul5LiL44GuM+mAmuOCigogICAgb2RhX19pCiAgICBvZF9fYWkKICAgIG9fX2RhaQoKICAgIFsyXSBvZGFpb2RhaSA9PiA1CgogICAgWzNdIG9vb29kZGRkYWFhYWlpaWkgPT4gMjU2CgogICAgWzRdIGRhaW9hZGlhbyA9PiAwIAoKPWVuZAoKJGFucyA9IDAKCmRlZiBjb21iaSggcGEsIGkgPSAwLCBuID0gLTEgKQoJcGFbaV0uZWFjaHt8cG58CgkJbmV4dAlpZiBwbiA8PSBuCgkJaWYgaSA8IHBhLmxlbmd0aCAtIDEKCQkJY29tYmkoIHBhLCBpKzEsIHBuICkKCQkJbmV4dAoJCWVuZAoJCSRhbnMgKz0gMQoJfQplbmQKCmRlZiBzb2x2ZSggcGF0LCBzdHIgKQoJcGEgPSBbXQoJaSA9IDAKCW4gPSAwCglwYXQuZWFjaF9jaGFye3xjaHwKCQlwbiA9IFtdCgkJd2hpbGUoIG4gPSBzdHIuaW5kZXgoY2gsbikgKQoJCQlwbiA8PCBuCgkJCW4gKz0gMQoJCWVuZAoJCWJyZWFrCWlmIHBuLmVtcHR5PwkjIOino+eEoeOBlwoJCXBhIDw8IHBuCgkJaSArPSAxCgkJbiA9IHBuLm1pbgoJfQoJJGFucyA9IDAKCWNvbWJpKCBwYSApCWlmIHBhLnNpemUgPT0gcGF0LnNpemUKCXB1dHMgJGFucwplbmQKCglwYXQgPSAib2RhaSIKCXNvbHZlKCBwYXQsICJvZGFkYWkiICkJCQkJIz0+IDMKCXNvbHZlKCBwYXQsICJvZGFpb2RhaSIgKQkJCSM9PiA1Cglzb2x2ZSggcGF0LCAib29vb2RkZGRhYWFhaWlpaSIgKQkjPT4gMjU2Cglzb2x2ZSggcGF0LCAiZGFpb2FkaWFvIiApCQkJIz0+IDAKCj1iZWdpbgoKCW8gZCBhIGQgYSBpCm8JMSAwIDAgMCAwIDAJCTAKZAkwIDEgMCAxIDAgMAkJMSwzCmEJMCAwIDEgMCAxIDAJCTIsNAppCTAgMCAwIDAgMCAxCQk1CgkwIDEgMiAzIDQgNQpbWzBdLCBbMSwgM10sIFsyLCA0XSwgWzVdXQoKCW8gZCBhIGkgbyBkIGEgaQpvCTEgMCAwIDAgMSAwIDAgMApkCTAgMSAwIDAgMCAxIDAgMAphCTAgMCAxIDAgMCAwIDEgMAppCTAgMCAwIDEgMCAwIDAgMQpbWzAsIDRdLCBbMSwgNV0sIFsyLCA2XSwgWzMsIDddXQoKb29vb2RkZGRhYWFhaWlpaQpbWzAsIDEsIDIsIDNdLCBbNCwgNSwgNiwgN10sIFs4LCA5LCAxMCwgMTFdLCBbMTIsIDEzLCAxNCwgMTVdXQoKZGFpb2FkaWFvCltbMywgOF0sIFs1XSwgWzQsIDddLCBbNl1dCltbMywgOF0sIFs1XSwgWzddXQkJIyDmnp3liIjjgoogMXBhc3Pjgafop6PnhKHjgZfnorrlrpoKCj1lbmQK