Pic1. 北京东路
Pic2. 北京东路
Pic3. 南京东路
恐怖分子在 个城市的北京东路上安装了炸弹，初始第 个城市中的炸弹威力为 。
恐怖分子决定进行 次爆炸。一次 城市的爆炸中，其危险度为这个城市中炸弹的威力 。每次爆炸之后，由于恐怖分子可以操控能量以保持炸弹总威力不变，对于任意 ， 将增加 ，而 将清零。
然而，恐怖分子的遥控爆炸系统坏了，每次都会随机选择一个城市进行爆炸。
为了方便防御，小 S 想知道进行 次爆炸后， 城市中炸弹的威力 的期望值是多少，对 取模。
第一行两个正整数 。
第二行 个正整数 。
一行， 个正整数，表示期望值。
6 3 2 1 0 0 3 5
381994841 86514512 789278536 789278536 677475170 270191475
2 1 1 2
499122178 499122178
对于所有数据：，，。
