I. In Search of Soles
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$n$$$ identical biased coins. In each toss, every coin shows sol with probability $$$\tfrac{p}{q}$$$ and águila with probability $$$1 - \tfrac{p}{q}$$$. Initially, none of the coins has shown sol.

You perform the following process:

  • In each round, you toss all coins that have not shown sol yet.
  • Once a coin shows sol for the first time, it is removed from further tosses.
  • The process continues until every coin has shown sol at least once.

Let $$$T$$$ denote the number of rounds until this happens. Your task is to compute the expected value of $$$T$$$.

Input

The input consists of three integers $$$n$$$, $$$p$$$, and $$$q$$$ ($$$1 \leq n \leq 10^7$$$, $$$1 \leq p \leq q \lt 998244353$$$), where $$$\tfrac{p}{q}$$$ is the probability that a coin shows heads in a single toss.

Output

Print a single integer: the expected number of rounds until all $$$n$$$ coins have shown sol, modulo $$$998244353$$$.

Examples
Input
1 1 2
Output
2
Input
2 1 2
Output
665496238