这题可以用非 $Lucas$ 做法水过
$Lucas$ 是可以过 $1e18$ 的
$CRT$ 模版也是，那道题的范围都不用 $exgcd$ 。
建议加强数据。违规紫衫。