beecrowd | 1398

Ocean Deep! Make it Shallow!!

By Shahriar Manzoor, SEU Bangladesh
Timelimit: 1

Ocean deep
I'm so afraid to show my feelings,
I have sailed a million ceilings
In my solitary room
Ocean deep

The lines above are from a very popular song of Cliff Richard. In this problem we will be dealing with a similar type of person. His name is Rampell-Stilt-Skin and another important thing is that he is a dead man. Someone has killed him a few days ago and you are the detective to solve the mystery. The problem with this guy is that he always tried to hide his information and feelings under the sea (I mean out of reach). He wrote a diary, which contained some statements and then a large binary number (May have as many as 10000 digits). If the number is divisible by a large prime number 131071 then the statement is true, otherwise the statement is false.

In this problem you will be given large binary numbers as input and you will have to verify if that number is divisible by 131071 or not. Your algorithm needs to be very efficient.

Input

The input file contains several binary numbers. Each binary number starts in a new line but may expand in several lines. Each number is terminated by a # symbol. No line contains more than 100 digits.

Output

For every binary number print "YES" if the number is divisible by the given prime number, print "NO" if the binary number is not divisible by the given prime number.

Sample Input Sample Output

0#
1010101#

YES
NO

“After my last exam of my undergraduate course, I discovered that I have studied boilers, electric motors,
mechanical drawing, accounting, professionalism in computer science, Continuous Mathematics, etc in
my undergraduate courses, but, I never had the chance to study Knuth’s ‘Concrete Mathematics’ in
any of my courses. So now, when I am reading it seriously, I realize that no one should be a
Computer Science (& Engineering) Graduate before reading this book. But, surely, I
would have to thank one of my teachers for letting me know about this book.”