Execution time limit is 1 second Runtime memory usage limit is 128 megabytes Consider an infinite sequence A defined as follows:
A0=1,
Ai=Ai/p+Ai/q,i≥1
You are given n,p and q. Find the value of An.
Input
Three integers n,p and q (0≤n≤1012,2≤p,q≤109).
Output
Print the value of An.
Examples