// Задача "Числа Фибоначчи"
// 8-ая Интернет-олимпиада сезона 2007-2008, базовый уровень
// Автор задачи: Антон Ахи
// Автор решения: Федор Царев, tsarev@rain.ifmo.ru

import java.io.*;
import java.util.*;

public class fib_ft implements Runnable {

	public final static int MAX_N = (int) 2e5;

	private Scanner in;
	private PrintWriter out;
	String fname = "fib";

	private void myAssert(boolean e, String message) {
		if (!e) {
			throw new Error("Assertion failure!!! " + message);
		}
	}                               

	public void solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		myAssert(1 <= n && n <= 1000000, "");
		myAssert(1 <= m && m <= 1000000, "");
		int x = -1;
		for (int i = 1; i <= Math.min(n, m); i++) {
			if (n % i == 0 && m % i == 0) {
				x = i;
			}
		}
		int[] fib = new int[Math.max(x + 1, 10)];
		fib[1] = 1;
		fib[2] = 1;
		for (int i = 3; i <= x; i++) {
			fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000000;
		}
		out.println(fib[x]);
	}

	public void run() {
		try {
			solve();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		} finally {
			out.close();
		}		
	}

	public fib_ft() {
		try {
			in = new Scanner(new File(fname + ".in"));
			out = new PrintWriter(new File(fname + ".out"));
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}


	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		new Thread(new fib_ft()).start();
	}

}                       