Problem: The FARIO Incident

Want to try solving this problem? You can submit your code online if you log in or register.

The FARIO Incident

Time Limit: 1 second
Memory Limit: 16 MB

You are a superspy. Your job requires you to travel around the world, visiting exotic locales and driving expensive cars. Your latest mission is to break into the headquarters of the evil F.A.R.I.O. organisation and steal important documents. Getting in is easy for a spy like you, but the documents are in a safe which can only be opened by entering the correct code into the keypad.

1	2	3
4	5	6
7	8	9

The keypad is a 3 x 3 grid numbered from 1 to 9, as shown above. Your sources tell you that every two consecutive digits in the code will always be adjacent keys on the keypad. For example, the digit 1 will only be followed by a 2 or 4, the digit 2 will only be followed by a 1, 3 or 5, and so on. So 3252 and 12369 are valid codes, but 1234 is not (3 is not adjacent to 4 on the keypad) and 55 is not (5 is not adjacent to 5 on the keypad).

You also know how many digits there are in the code, and the first digit. Given this information, how many possible secret codes are there?

Input

Your program must read from standard input. The input will consist of two space-separated integers, N and D. N is the number of digits in the code (1 ≤ N ≤ 1,000,000), and D is the first digit (1 ≤ D ≤ 9).

For 30% of the available marks, N ≤ 10.

Output

Your program must write to standard output. The output should consist of a single integer: the number of possible codes, modulo 1,000,003.

Sample Input 1

3 4

Sample Output 1

Sample Input 2

42 8

Sample Output 2

Explanation

In sample input 1, a code of length 3 and starting from the digit 4, the possible codes are 412, 414, 452, 454, 456, 458, 474 and 478.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.