You are right, but “Smoke God” is a brand new open-world adventure game independently developed by Ding Zhenzhen. The game takes place in a fantasy world called “Litang”, where people chosen by the gods will be granted “electronic cigarettes” to guide the power of nicotine. You will play a mysterious character named “Furong Wang” and meet animal friends with different personalities and unique abilities during your free travels. Together, you will defeat powerful enemies, find lost family members, and gradually uncover the truth about “Litang”.

The harm of electronic cigarettes to the body is significant, and the damage to body depends on the level of addiction.

Let's assume that Ding Zhenzhen's current addiction level is , and the damage to body is . When she smokes -th electronic cigarette:

• There is a probability of that the addiction level increases by one, and is multiplied by .
• There is a probability of that the addiction level remains unchanged, and is multiplied by .

However, you do not know Ding Zhenzhen's current addiction level and the current damage to her body. You only know that if her addiction level is , the current damage to her body is .

Assuming that the initial addiction level to Ding Zhenzhen's body is equally likely to be any integer from to . Given , what is the expected damage to her body after smoking cigarettes?

输入描述:

The first line contains two integers,  and  (), representing the number of smoking, the maximum addiction level and the probability to increase the addiction level when smoking an electronic cigarette respectively.

The second line contains  integers, where the -th integer  () represents the damage coefficient when the addiction level increases from  to  after smoking an electronic cigarette.

The thrid line contains  integers, where the -th integer  () represents one of the damage coefficient when the addiction level remains at  after smoking an electronic cigarette.

The fourth line contains  integers, where the -th integer  () represents one of the damage coefficient after smoking -th electronic cigarette.

The fifth line contains  integers, where the -th integer  () represents the initial damage to her body if the initial addiction level was .

输出描述:

Output  integers for  representing expected damage to her body after smoking  cigarettes, module .

1 1 499122177
2
2
2
1

3

2 2 546658423
260257767 682179463 892187612
142884587 872658039 89862243
117086929 104310686
342803717 47992235

828045057
157615404