sub egcd($$) {
    my ($a,$b) = @_;

    if ($a<0) {
	my ($d,$x,$y) = egcd(-$a,$b);
	return ($d,-$x,$y);
    } elsif ($b<0) {
	my ($d,$x,$y) = egcd($a,-$b);
	return ($d,$x,-$y);
    } elsif ($a<$b) {
	my ($d,$x,$y) = egcd($b,$a);
	return ($d,$y,$x);
    } elsif ($b==0) {
	return ($a,1,0);
    } else {
	my $k = $a/$b;
	my ($d,$x,$y) = egcd($a-$k*$b,$b);
	return ($d,$x,$y - $k*$x);
    }
}