cho.sh
Notes
Loading...

Infinite Sequence

Time limit

2s

Memory limit

128 MB

Problem

An infinite sequence A is defined as follows.

  • A_0 = 1
  • For i ≥ 1, A_i = A_⌊i / P⌋ + A_⌊i / Q⌋

Given integers N, P, and Q, write a program that computes A_N.

Input

The first line contains three integers N, P, and Q separated by spaces.

Output

Print the value of A_N.

Constraints

  • 0 ≤ N ≤ 10^12
  • 2 ≤ P, Q ≤ 10^9

Hint

⌊x⌋ is the greatest integer that is not greater than x.