← 返回题目列表

Codeforces · 374/B

B. 伊娜和九

中文机器翻译题面 查看原题

Inna 非常喜欢数字 9。这就是为什么她要求迪玛写一个由9组成的小数字。但迪玛肯定误会了她的意思,他写了一个很大的数字a,由1到9的数字组成。

Inna 想稍微改变 Dima 写的数字,以便最终该数字包含尽可能多的数字 9。 Inna 可以一步选择数字中总和等于 9 的两个相邻数字,并将其替换为单个数字 9。

例如,Inna 可以这样修改数字 14545181:14545181 → 1945181 → 194519 → 19919。此外,她可以使用此方法将数字 14545181 转换为数字 19991。Inna 不会将其转换为 149591,因为她可以获取数字19919 和 19991 包含更多数字 9。

Dima 是一名程序员,因此他想找出 Inna 可以从所写的数字中得到多少个包含尽可能多的数字 9 的不同数字。帮助他完成这项具有挑战性的任务。

输入

输入的第一行包含整数 a (1 ≤ a ≤ 10100000)。数字 a 没有任何零。

输出

在一行中打印一个整数——问题的答案。保证问题的答案不超过263 - 1。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

369727

输出 #1

2

输入 #2

123456789987654321

输出 #2

1

输入 #3

1

输出 #3

1

注意

样本注释

在第一个样本中,Inna 可以获得以下数字:369727 → 99727 → 9997、369727 → 99727 → 9979。

在第二个示例中,Inna 可以执行如下操作:123456789987654321 → 12396789987654321 → 1239678998769321。