978. Интересный треугольник

Как известно, любимая задача программеров всего мира формулируется так: найти сумму элементов `N`-ой строки треугольника Паскаля. Известны многочисленные варианты этой задачи. Так в одном из наших турниров была предложена исключительно красивая задача о нахождении суммы биномиальных коэффициентов `C(N,1)+…+C(N,N)`. Когда-нибудь жюри ещё вернётся к этой прекрасной задаче, но сегодня мы рассмотрим другие свойства треугольника Паскаля. Этот интересный математический объект обладает совершенно фантастическими свойствами! Например, `N`-я строка содержит ровно `N+1` элемент!!! Наука до сих пор не смогла объяснить этот поразительный факт! Но сейчас давайте решим более простой вопрос – сколько чисел в `N`-ой строке треугольника Паскаля не делится на заданное простое число `P`?

Во входном файле записано число `N` (`0\ ≤\ N\ ≤\ 1\ 000\ 000\ 000`) и простое число `P` (`P\ <\ 1000`).

Запишите в выходной файл количество чисел в `N`-ой строке треугольника Паскаля, не делящихся на `P`.

4 3

4

48 3

12