Prize X26770

Ronald Zynoulus has invented a new board game. The game is played by two players on a board composed of green, white and black hexes. One player plays with blue stones, and the other with red stones. Initially each hex contain exactly one stone. Then, players alternate moves. Consider a stone of color C at some position P. Let P+1, …, P+d be a sequence of positions in a straight line from P (there are 6 possible directions). If P+d contains another stone of color C, and P+1 … P+(d−1) contain stones of the other color, these other stones can be removed by the owner of color C. There are also rules regarding movement of stones.

Anyway, Ronald has shown his game to Gill Bytes, one of the wealthiest men in Meashara. Gill enjoyed the game very much, and has offered Ronald a prize for it. Ronald wanted to receive one Measharan cent for each possible initial configuration of R red and B blue stones. Gill agreed, and has asked you to calculate the answer.

Gill pays attention to details, and thus you have to calculate the last 9 digits of the prize, given in the greatest monetary unit which evenly divides it. Ten Measharan cents make one dime, ten dimes make one dollar, ten dollars make one hamilton, and so on: each following monetary unit equals 10 units of the previous rank. Thus, for example, if the prize was 123451234500 cents, then this is equal to 1234512345 dollars, and you need to print last 9 digits of that number (234512345).

Input

The first and only input line contains two numbers R and B, 1 ≤ R, B ≤ 10¹5.

Output

If the prize has at most 9 digits, give all of its digits (except leading zeros). Otherwise give 9 last digits.