题目描述

The Department of Defense (DoD) has developed a new wireless technology that is claimed to be unpenetrable. This new technology consists of two types of devices: a transmitter and a receiver. Even though the DoD has tried to make those devices to be robust, the new transmitter might be spoilt depending on the cause. The new receiver, on the other hand, is quite robust and designed such that it cannot be turned off. The receiver is online if only if at least one of the following conditions is satisfied.

• There exists 2 active transmitters (not spoilt) such that the receiver is located exactly at a line segment connecting those 2 transmitters.
• There exists 3 active transmitters (not spoilt) such that the receiver is located strictly inside a triangle formed by those 3 transmitters.

This new technology allows the DoD to strategically place their communication towers such that their military bases cannot be tapped by an outsider. There are $N$ military bases each located at a coordinate $(x_i, y_i)$ and $M$ communication towers each located at a coordinate $(x_j, y_j)$. Each military base is equipped with a new receiver, and each communication tower is equipped with a new transmitter. It is guaranteed that there is no pair of buildings (i.e. military bases or communication towers) that are located at the same location. It is also guaranteed that the receiver in each military base is online, thus, all military bases are online.

One day, the DoD predicts that a heavy storm will come close to its communication towers. During this heavy storm, each transmitter has a chance of $(100 - S)\%$ to be spoilt and $S\%$ to survive (or not to be spoilt).

The DoD asks your help to calculate the probability that all the military bases are still online right after the heavy storm. This probability can be expressed as a rational number $\frac{P}{Q}$ where $P$ and $Q$ are two coprime integers. You should output an integer $P \cdot Q^{-1} \pmod{998\,244\,353}$ where $Q^{-1}$ is the modular inverse of $Q$ modulo $998\,244\,353$. In other words, you should output an integer $R$ ($0 \leq R < 998\,244\,353$) such that $P \equiv Q \cdot R \pmod{998\,244\,353}$.

输入格式

Input begins with a line containing three integers: $N\ M\ S$ ($1 \leq N \leq 500$; $2 \leq M \leq 500$; $0 < S < 100$) representing the number of military bases, the number of communication towers, and the probability of a transmitter not to be spoilt due to the heavy storm, respectively. The next $N$ lines each contains two integers: $x_i\ y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$) representing the location of each military base. The next $M$ lines each contains two integers: $x_j\ y_j$ ($-10^9 \leq x_j, y_j \leq 10^9$) representing the location of each communication tower. It is guaranteed that there are no buildings (i.e. military bases or communication towers) that are located at the same location. It is also guaranteed that all military bases are online before the heavy storm.

输出格式

Output in a line an integer $R$ ($0 \leq R < 998\,244\,353$) such that $P \equiv Q \cdot R \pmod{998\,244\,353}$ where $P$ and $Q$ are two coprime integers and $\frac{P}{Q}$ is the probability that all the military bases are still online right after the heavy storm.

1 4 50
0 0
-1 0
3 0
0 1
2 -1

686292993

3 5 20
3 0
1 3
5 3
0 0
0 6
6 0
6 6
3 3

771443236

提示

Explanation for the sample input/output #1

Each transmitter has a chance of $50\%$ to survive the heavy storm. In this case, there are $16$ possible outcomes with the same probability, and only $5$ of them cause all the military bases to be still online right after the heavy storm, i.e. the set of active transmitters (not spoilt) are either of the following: $\{1, 2\}$, $\{1, 2, 3\}$, $\{1, 2, 3, 4\}$, $\{1, 2, 4\}$, and $\{1, 3, 4\}$. Therefore, the probability is $\frac{5}{16}$, hence $P = 5$, $Q = 16$, and $R = 686\,292\,993$.

Explanation for the sample input/output #2

All transmitters except the $5^{th}$ transmitter must not be spoilt so that all the military bases are still online right after the heavy storm. With each transmitter having a chance to survive of $20\%$ or $\frac{1}{5}$, the probability of such a case is $\left(\frac{1}{5}\right)^4 = \frac{1}{625}$. Therefore, $P = 1$, $Q = 625$, and $R = 771\,443\,236$.