时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
题目描述
wzj is working on a cloze test. For those who are not familiar with cloze tests, here is an introduction:
A cloze test consists of
questions, each with exactly 
options. A sequence of positive integers between 1 and is called an answer set.
The standard answer to the cloze test is a specific answer set. The score of an answer set is defined as the number of positions where it matches the standard answer. An answer set is called balanced if each integer from 1 to appears exactly the same number of times (in this problem, is guaranteed to be a multiple of ). The standard answer is always balanced.
Here is some information about wzj:
wzj has a clear understanding of his own level in cloze tests. He knows that he has a probability
of scoring exactly 
. This means he has a probability 
of getting all wrong, a probability 
of getting exactly 1 correct, ..., and a probability 
of getting all correct. wzj selects among answers with the same score uniformly at random. That is, wzj's process of completing the cloze test is as follows: he first randomly determines his score according to the probabilities , and then randomly selects one answer set among those that achieve this score.
Given this background:
A cloze test consists of
The standard answer to the cloze test is a specific answer set. The score of an answer set is defined as the number of positions where it matches the standard answer. An answer set is called balanced if each integer from 1 to
Here is some information about wzj:
wzj has a clear understanding of his own level in cloze tests. He knows that he has a probability
Given this background:
One day, wzj completed a cloze test and was pleasantly surprised to find that his answer was balanced. Calculate the expected value of his score. Output the result modulo 
.
输入描述:
The first line contains two positive integersand
, indicating the number of questions and the number of options for each question. It is guaranteed that
The second line containsnon-negative integers
, representing the probability of wzj scoring each possible score. The sum of
is guaranteed to be 1 modulo
.
输出描述:
A single integer representing the expected value of wzj's score modulo
示例3
备注:
.
.
Ensure that the denominator is not a multiple of