Description

In a particular language words are written using only two symbols: ones(1) and zeroes(0). A given word N is called “good” if it can be written in the form of concatenation of several(two or more than two) copies of some shorter word, and is called bad otherwise.

For example the words 100, 1100, 0010 are “bad”, while the words 0101, 001001 are “good”.

The task is to calculate the number T of good words which can be formed using exactly a ones and b zeroes.

Report your answer as T modulo 10⁷+1

Input Format

First line contains the number of zeroes Seconds line contains the number of ones

Output Format

One line containing the maximum number of "good" words that can be formed taken modulo 10⁷+1

Input Limits

0 <= a, b <= 5000