У Алана есть n башен, у каждой из которых есть параметр a[i] - числитель рук и параметр b[i] - знаменатель рук. В q очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - |a[i] / b[i]| (округление вниз) или дробное количество рук - a[i] / b[i]. Для i-го дела, которые он задумал, Алану необходимо суммарно ровно x[i] рук. Для каждого из этих дел Алан берет все n башен, то есть суммарная рукость всех башен должна равняться x[i]. Помогите Алану найти количество способов сделать это, для каждого из q легких дел.
Мысли по задаче: На 51 балл написал перебор масок, после попытался использовать MITM, надеясь на то, что количество целых рук мало(это оказалось не так).
Помогите с решением этой задачи на 100