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

public class fib_af implements Runnable {
  public static void main(String[] args) {
    new Thread(new fib_af()).start();
  }

  BufferedReader br;
  StringTokenizer st;
  PrintWriter out;
  boolean eof;

  public void run() {
    try {
      String FNAME = "fib";
      Locale.setDefault(Locale.US);
      br = new BufferedReader(new FileReader(FNAME + ".in"));
      out = new PrintWriter(FNAME + ".out");
      solve();
    } catch (IOException e) {
      e.printStackTrace();
    } finally {
      out.close();
    }
  }

  String nextToken() {
    while (st == null || !st.hasMoreElements()) {
      try {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) {
        eof = true;
        return "0";
      }
    }
    return st.nextToken();
  }

  int nextInt() {
    return Integer.parseInt(nextToken());
  }

  long nextLong() {
    return Long.parseLong(nextToken());
  }

  double nextDouble() {
    return Double.parseDouble(nextToken());
  }

  Random rand = new Random(this.hashCode());

  void myAssert(boolean e, String msg) {
	  if (!e) {
		  throw new Error(msg);
	  }
  }
  
  int gcd(int n, int m) {
	  return (n == 0) ? m : gcd(m % n, n);
  }
  
  int P = 1000000000;
  
  int f1 = 0, f2 = 1;
  
  int fib(int n) {
	  if (n == 1) return f2;
	  int t = f2;
	  f2 = (f1 + f2) % P;
	  f1 = t;
	  return fib(n - 1);
  }
  
  void solve() throws IOException {
	  int n = nextInt();
	  myAssert(1 <= n && n <= 1000000, "n out of bounds");
	  int m = nextInt();
	  myAssert(1 <= m && m <= 1000000, "m out of bounds");
	  out.println(fib(gcd(n, m)));
  }
}
