Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3341
Voyager 1

Time Limit: 10 Seconds      Memory Limit: 32768 KB

We all know that Voyager 1 spacecraft is currently the farthest man-made object from Earth, traveling away from both the Earth and the Sun at a speed that corresponds to a greater specific orbital energy than any other probe. And Voyager 1's Saturnian flyby occurred in November 1980, with the closest approach on November 12, 1980, when the space probe came within 124,000 kilometers (77,000 mi) of Saturn's cloud-tops. The space probe's cameras detected complex structures in the rings of Saturn, and its remote sensing instruments studied the atmospheres of Saturn and its giant moon Titan. Because Pioneer 11 had one year earlier detected a thick, gaseous atmosphere over Titan, the Voyager space probes' controllers at the Jet Propulsion Laboratory elected for Voyager 1 to make a close approach of Titan.

During this close approach of Titan, Voyager 1 had received some strange information from Titan. Through the efforts of researchers, we found the information encoding. The information can be parted to several paragraphs, each contains two large decimal numbers A and B, one small decimal number L and a string of symbols. And in each paragraph, the small decimal number equals to the length of the string of symbols, symbols only contains plus sign, minus sign, and multiplication sign. According to some NASA's top-secret files of Titan, researchers found that each paragraph's meaning was a large decimal numbers, which was based on the operations described by the string of symbols.

The string of symbols only contains plus sign, minus sign, and multiplication sign, and they did mean plus, minus and multiplication, but researchers found that after each operation, the real result was the remainder of the result divide the product of primes under 1000. Researchers wrote down B on the right of A, did the first operation the string described, and put the real result on the right of B. Then they did the second operation on B and the first result, and put the real result on the right of the first result. They did each operation on the two most right-hand numbers, and wrote down the real result on the right. After all L operations, the most right-hand number represents the paragraph's meaning.

Now your task is: show the researchers all the paragraphs' meaning. If you have some difficulties in understanding the operations, just see our sample input and sample output carefully.


There are several paragraphs.

In each case, there will be two non-negative decimal numbers A and B, both A and B is less than the product of primes under 1000. The following line contains a integer L(1 <= L <= 300000), which represents the length of the following string of symbols. Then the following line contains a string, which length equals to L, and only contains plus sign, minus sign, and multiplication sign. There is no consecutive 110 plus sign, minus sign or multiplication sign. And the researchers found that over 50 percent of the string of symbols is a multiplication sign.

In order to make our sample input and output easier to print, we added some "\" symbols into the large decimal numbers and divided them into several lines. You have to understand that both the "\" symbol and the line break will not appear in the large numbers of the real input, and you cannot use them to separate your large numbers in output either.


For each paragraph, output the decimal number represents the paragraph's meaning in one line.

Sample Input


Sample Output



The product of primes under 1000 equals to
and there are 168 primes under 1000.

Author: FAN, Yuzhe
Source: ZOJ Monthly, May 2010
Submit    Status