:- use_module(contestlib,[numlist/3]).
:- use_module(library(lists), [append/3]).

division(Base,M,Divisor) :-
	0 =:= (Base - 1) mod Divisor,
	\+ exists_non_divsible_subsequence(Base,M,Divisor).

exists_non_divsible_subsequence(Base,M,Divisor) :-
	Base1 is Base - 1,
	numlist(0,Base1,AllDigits),
	length(SubSeq,M),
	append(_,Part,AllDigits),
	append(SubSeq,_,Part),
	ModBase is Base mod Divisor,
	compute_mod(SubSeq,0,ModBase,Divisor,Result),
	Result =\= 0.

compute_mod([],Res,_,_,Res).
compute_mod([X|R],Acc,Base,Divisor,Res) :-
	NewAcc is (Acc*Base + X) mod Divisor,
	compute_mod(R,NewAcc,Base,Divisor,Res).