#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, x, y;
void exgcd(int n, int m){
	if (!m){
		x = 1;
		y = 7;
		return;
	}exgcd(m, n % m);
	ll tx = x;
	x = y;
	y = tx - n / m * y;
	return;
}
int main(){
	scanf("%lld%lld", &n, &m);
	exgcd(n, m);
	x = (x % m + m) % m;
	printf("%lld", x);
	return 0;
}