Inna loves digit 9 very much. That's why she asked Dima to write a small number consisting of nines. But Dima must have misunderstood her and he wrote a very large number a, consisting of digits from 1 to 9.

Inna wants to slightly alter the number Dima wrote so that in the end the number contained as many digits nine as possible. In one move, Inna can choose two adjacent digits in a number which sum equals 9 and replace them by a single digit 9.

For instance, Inna can alter number 14545181 like this: 14545181 → 1945181 → 194519 → 19919. Also, she can use this method to transform number 14545181 into number 19991. Inna will not transform it into 149591 as she can get numbers 19919 and 19991 which contain more digits nine.

Dima is a programmer so he wants to find out how many distinct numbers containing as many digits nine as possible Inna can get from the written number. Help him with this challenging task.


-----Input-----

The first line of the input contains integer a (1 ≤ a ≤ 10^100000). Number a doesn't have any zeroes.


-----Output-----

In a single line print a single integer — the answer to the problem. It is guaranteed that the answer to the problem doesn't exceed 2^63 - 1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
369727

Output
2

Input
123456789987654321

Output
1

Input
1

Output
1



-----Note-----

Notes to the samples

In the first sample Inna can get the following numbers: 369727 → 99727 → 9997, 369727 → 99727 → 9979.

In the second sample, Inna can act like this: 123456789987654321 → 12396789987654321 → 1239678998769321.

Source: codeforces | Difficulty: MEDIUM
Tags: Combinatorics

Greedy algorithms


Solutions:
3

def readln():
	return list(map(int, input().split()))
ans = 1
l = 1
p = -1
a = input()
for i in range(len(a)):
	c = int(a[i])
	if c + p == 9:
		l += 1
	if c + p != 9 or i == len(a) - 1:
		if l % 2:
			ans *= (l + 1) // 2
		l = 1
	p = c
print(ans)


s = input()
n = len(s)
ans = 1
cnt = 1
for i in range(n - 1):
	if int(s[i]) + int(s[i + 1]) == 9:
		cnt += 1
	else:
		if cnt % 2 == 1:
			ans = ans * (cnt // 2 + 1)
		cnt = 1
if cnt % 2 == 1:
	ans = ans * (cnt // 2 + 1)
print(ans)


(s, a, c) = (input(), 1, 1)
for i in range(1, len(s)):
	if int(s[i]) + int(s[i - 1]) == 9:
		c += 1
	elif c % 2:
		a *= c // 2 + 1
		c = 1
	else:
		c = 1
if c % 2:
	a *= c // 2 + 1
print(a)


a = input()
ans = 1
LIM = 100000 + 12
run = [0 for i in range(LIM)]
for i in range(1, LIM, 2):
	run[i] = 1
run[0] = 1
run[2] = 2
for i in range(4, LIM, 2):
	run[i] = run[i - 2] + run[i - 3]
lst = 0
for i in range(1, len(a)):
	sm = int(a[i]) + int(a[i - 1])
	if sm != 9:
		ans *= run[lst]
		lst = 0
	else:
		lst += 1
ans *= run[lst]
print(ans)


a = input()
n = len(a)
ans = 1
block = 0
for i in range(n):
	if i == n - 1 or int(a[i]) + int(a[i + 1]) != 9:
		if block > 0 and block % 2 == 0:
			ans *= block // 2 + 1
		block = 0
	else:
		block += 1
print(ans)


n = input()
l = len(n)
ans = 1
i = 0
while i < l:
	x = 1
	while i < l - 1 and int(n[i]) + int(n[i + 1]) == 9:
		x += 1
		i += 1
	if x % 2 == 1 and x > 1:
		ans *= x // 2 + 1
	x = 1
	i += 1
print(ans)


class CodeforcesTask374BSolution:

	def __init__(self):
		self.result = ''
		self.number = []

	def read_input(self):
		self.number = [int(c) for c in input()]

	def process_task(self):
		nums = 1
		x = 0
		while x + 1 < len(self.number):
			s = 1
			while self.number[x] + self.number[x + 1] == 9:
				s += 1
				x += 1
				if x + 1 >= len(self.number):
					break
			if s > 2:
				if s % 2:
					nums *= s // 2 + 1
			x += 1
		self.result = str(nums)

	def get_result(self):
		return self.result
Solution = CodeforcesTask374BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import stdin, stdout
from io import BytesIO, IOBase
from itertools import accumulate
from collections import deque

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a
res = set()

def solve(p, l, a, b):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solve(p * 10 + a, l + 1, a, b)
	solve(p * 10 + b, l + 1, a, b)
n = input()
l = len(n)
ans = 1
i = 0
while i < l:
	x = 1
	while i < l - 1 and int(n[i]) + int(n[i + 1]) == 9:
		x += 1
		i += 1
	if x % 2 == 1 and x > 1:
		ans *= x // 2 + 1
	x = 1
	i += 1
print(ans)


s = input()
ans = 1
n = len(s)
c = 1
for i in range(1, n):
	if int(s[i]) + int(s[i - 1]) - 2 * int('0') == 9:
		c += 1
	else:
		if c % 2 == 1 and c > 1:
			ans *= (c + 1) // 2
		c = 1
if c % 2 == 1 and c > 1:
	ans *= (c + 1) // 2
print(ans)


import sys

def solve():
	a = list(map(int, list(input())))
	res = 1
	curcount = 1
	for i in range(1, len(a)):
		if a[i] + a[i - 1] == 9:
			curcount += 1
		else:
			if curcount > 2 and curcount % 2 == 1:
				res *= curcount // 2 + 1
			curcount = 1
	if curcount > 2 and curcount % 2 == 1:
		res *= curcount // 2 + 1
	return res
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
print(solve())


n = input()
i = 0
count = 1
a = 1
for i in range(1, len(n)):
	if int(n[i]) + int(n[i - 1]) == 9:
		count += 1
	elif count % 2 != 0:
		a *= count // 2 + 1
		count = 1
	else:
		count = 1
if count % 2 != 0:
	a *= count // 2 + 1
print(a)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest, _heapify_max, _heapreplace_max
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def outln(var):
	sys.stdout.write(str(var) + '\n')

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
s = data()
index = dd(set)
j = 0
n = len(s)
for i in range(n - 1):
	if int(s[i]) + int(s[i + 1]) == 9:
		index[j].add(i)
		index[j].add(i + 1)
	else:
		j += 1
answer = 1
for i in index.keys():
	if len(index[i]) & 1:
		answer *= ceil(len(index[i]) / 2)
outln(answer)


p = 10
cnt = 0
r = 1
for c in input():
	c = int(c)
	if c + p == 9:
		cnt += 1
	else:
		if cnt > 0 and cnt % 2 == 0:
			r *= cnt // 2 + 1
		cnt = 0
	p = c
if cnt > 0 and cnt % 2 == 0:
	r *= cnt // 2 + 1
print(r)


a = [int(x) for x in input()]
ans = 1
len_run = 0
for i in range(0, len(a) - 1):
	if a[i] + a[i + 1] == 9:
		len_run += 1
	elif len_run != 0:
		if len_run % 2 == 0:
			ans *= int(len_run / 2) + 1
		len_run = 0
if len_run != 0:
	if len_run % 2 == 0:
		ans *= int(len_run / 2) + 1
print(ans)


s = input()
ans = 0
i = 1
past = int(s[0])
c = 1
ans = 1
while i < len(s):
	if int(s[i]) + past == 9:
		c += 1
		past = int(s[i])
	else:
		if c % 2 == 1 and c != 1:
			ans *= c // 2 + 1
		c = 1
		past = int(s[i])
	i += 1
if c != 1 and c % 2 == 1:
	ans *= c // 2 + 1
print(ans)


a = input()
ans = 1
count = 1
l = len(a)
for i in range(l - 1):
	if int(a[i]) + int(a[i + 1]) == 9:
		count += 1
	else:
		if count % 2:
			ans *= (count + 1) // 2
		count = 1
if count % 2:
	ans *= (count + 1) // 2
print(ans)


n = input()
res = 1
countConsecutivePairs = 0
length = len(n)
for i in range(length):
	if i + 1 < length and int(n[i]) + int(n[i + 1]) == 9:
		countConsecutivePairs += 1
	else:
		if countConsecutivePairs % 2 == 0:
			res *= countConsecutivePairs // 2 + 1
		countConsecutivePairs = 0
print(res)


s = input()
b = 0
ans = 1
for i in range(len(s) - 1):
	if int(s[i]) + int(s[i + 1]) == 9:
		b += 1
	else:
		b += 1
		if b == 3:
			ans *= 2
			continue
		if b > 1 and b % 2 == 1:
			ans *= (b - 3) // 2 + 2
		b = 0
b += 1
if b > 1 and b % 2 == 1 and (b != 3):
	ans *= (b - 3) // 2 + 2
if b == 3:
	ans *= 2
print(ans)


t = input()
(s, d) = (0, 1)
p = {str(i): str(9 - i) for i in range(10)}
for i in range(len(t) - 1):
	if p[t[i]] == t[i + 1]:
		s += 1
	elif s:
		if s % 2 == 0:
			d *= s // 2 + 1
		s = 0
if s % 2 == 0:
	d *= s // 2 + 1
print(d)


a = list(map(int, list(input()))) + [1 << 35]
n = len(a)
ret = 1
cnt = 1
for i in range(1, n):
	if a[i] + a[i - 1] == 9:
		cnt += 1
	else:
		if cnt & 1:
			ret *= cnt // 2 + 1
		cnt = 1
print(ret)


import sys
import math
data = sys.stdin.read().split()
data_ptr = 0

def data_next():
	global data_ptr, data
	data_ptr += 1
	return data[data_ptr - 1]
S = data[0]
N = len(S)
ans = 1
block = 0
for i in range(N):
	if i == N - 1 or int(S[i]) + int(S[i + 1]) != 9:
		if block > 0 and block % 2 == 0:
			ans *= block // 2 + 1
		block = 0
	else:
		block += 1
print(ans)


def nine(s):
	(n, result, count) = (len(s), 1, 1)
	for i in range(n - 1):
		if int(s[i]) + int(s[i + 1]) == 9:
			count += 1
		else:
			if count % 2 == 1:
				result = result * (count // 2 + 1)
			count = 1
	if count % 2 == 1:
		result = result * (count // 2 + 1)
	return result
print(nine(input()))


s = input()
n = len(s)
i = k = p = 1
while i < n:
	while i < n and int(s[i]) + int(s[i - 1]) == 9:
		k += 1
		i += 1
	if k % 2 != 0:
		p *= (k + 1) // 2
	k = 1
	i += 1
print(p)


s = input()
nine = []
num = 0
ans = 1
for i in range(1, len(s)):
	if int(s[i - 1]) + int(s[i]) == 9:
		num += 1
	elif num > 0:
		nine.append(num + 1)
		num = 0
if num != 0:
	nine.append(num + 1)
for i in range(len(nine)):
	x = nine[i]
	if x % 2 != 0:
		ans = ans * int((x + 1) / 2)
print(ans)


num = input()
odd = 0
out = 1
for i in range(1, len(num)):
	if int(num[i]) + int(num[i - 1]) == 9:
		odd += 1
	elif odd % 2 == 0 and odd != 0:
		out *= odd // 2 + 1
		odd = 0
	else:
		odd = 0
if odd % 2 == 0 and odd != 0:
	out *= odd // 2 + 1
print(out)


from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	n = li()
	n.append(10)
	cnt = 0
	ans = 1
	ln = len(n)
	for i in range(1, ln):
		if int(n[i]) + int(n[i - 1]) == 9:
			cnt += 1
		else:
			ans *= (cnt + 1) // 2 + 1 if cnt % 2 == 0 else 1
			cnt = 0
	print(ans)
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def count_nine(a, i):
	while i < len(a) - 1:
		if a[i] + a[i + 1] == 9:
			break
		i += 1
	else:
		return (0, 1)
	(n1, c1) = count_nine(a, i + 1)
	(n2, c2) = count_nine(a, i + 2)
	if n1 == n2 + 1:
		return (n2 + 1, c1 + c2)
	else:
		return (n2 + 1, c2)

def count_nine2(a):
	n_list = [0] * (len(a) + 1)
	c_list = [0] * (len(a) + 1)
	c_list[-1] = c_list[-2] = 1
	for i in range(len(a) - 2, -1, -1):
		if a[i] + a[i + 1] == 9:
			n_list[i] = n_list[i + 2] + 1
			if n_list[i + 1] == n_list[i + 2] + 1:
				c_list[i] = c_list[i + 1] + c_list[i + 2]
			else:
				c_list[i] = c_list[i + 2]
		else:
			n_list[i] = n_list[i + 1]
			c_list[i] = c_list[i + 1]
	return (n_list[0], c_list[0])
(n, c) = count_nine2([int(x) for x in input()])
print(c)


s = input()
n = len(s)
k = 1
p = 1
for i in range(n - 1):
	if (int(s[i]) + int(s[i + 1])) % 9 == 0 and s[i] != '9' and (s[i] != '0'):
		k += 1
	else:
		if k > 1 and k % 2 == 1:
			p *= (k + 1) // 2
		k = 1
if k > 1 and k % 2 == 1:
	p *= (k + 1) // 2
print(p)