Nikolayın problemi

Nikolay n (n ≤ 10^18) uşağa hədiyyələri çatdırmalıdır. Onu bunu etmək üçün neçə variantın olduğu maraqlandırır. Sizə bu sualı cavablandırmaq lazımdır. Bu sayın çox böyük olduğunu nəzərə alaraq, cavabı m (m ≤ 2009) moduluna görə verin.

Giriş verilənləri

Tək sətirdə n və m natural ədədləri verilir.

Çıxış verilənləri

Variantların sayını verin.

Nümunələr