All Tracks Algorithms Problem

Ash and shopping
Tag(s):

Divide And Conquer, FFT, Generating Functions, Medium-Hard

Problem
Editorial
Analytics

Ash goes to a shop which has $$n$$ different items. The price of each of the items is $$1$$ unit . Ash is a rich guy and has infinite coins each of value $$k$$ units. Now he wants to buy some of the items, but he wants to make sure that he can pay for all the items he buys using the coins he has. Formally, the total price of the items he buys must be a multiple of $$k$$.
Find the number of ways in which he can buy some of the items from the shop. Since this number can be pretty huge, print only last 5 digits of the answer.
Two ways are considered distinct if there exists an $$i$$, such that item $$i$$ is bought in only one of them. Buying no item is also a valid way.

Input:
The only line in the input contains two integers separated by a space, $$n$$ and $$k$$.

Output:
Print the last 5 digits of the number of ways in which he can buy some of the items, as specified above.

Constraints:
$$1 \leq n \leq 10^{13} $$
$$ 1 \leq k \leq 10^4 $$

SAMPLE INPUT
3 2
SAMPLE OUTPUT
4
Explanation

Ash can buy either $$0$$ items in $$1$$ way or $$2$$ items in $$3$$ ways. So, the total number of ways is $$4$$

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications