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.

Difficulty: interview

Starter code:

Solutions:
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)
        
    
    


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()
ans=1
n=len(s)
c=1
for i in range(1,n):
    #print("i is",i,' and c is',c)
    if(int(s[i])+int(s[i-1])-2*int('0')==9):
        #print('s[i]+s[i-1]==9')
        c+=1
    else:
        #print('else')
        if(c%2==1 and c>1):
            #print('c%2==1 and c>1')
            ans*=(c+1)//2
            #print('ans is',ans)
        c=1
if(c%2==1 and c>1):
    ans*=(c+1)//2
print(ans)


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)

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)

# -*- coding: utf-8 -*-

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)

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())

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)


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)

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)

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)


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)


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)


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)


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)


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)


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)


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)


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)



# Made By Mostafa_Khaled


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
    else:
        if 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)



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)


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)

s = input()
n = len(s)
res = 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:
            res = res * (cnt // 2 + 1)
        cnt = 1
if cnt % 2 == 1:
  res = res * (cnt // 2 + 1)
print(res)