As you know, Chandler's work is something with numbers and no one knows what exactly it is. Today he has been assigned a task with hexadecimal numbers.

He is given a number n in hexadecimal. A new number can be made from the number n by selecting any subsequence of it (in HexaDecimal) and rearranging it. He has tell the number of distinct numbers that can be made from number n.

But Chandler has a date with Monica so he needs your help to solve this problem.

Since the answer will be very large, output the answer as modulo 10^9+7.

Constraints

n <= 2^8000 (n in decimal)

Input

Input contains a single line containing the input number in hexadecimal.

Output

Print the desired result

Problem Setter - Chanchur Bansal