有一个长度 的数组 ，可以对数组 进行任意排列。问：经过排列后，数组 进行"交替加乘”运算得到最大的结果是多少。
“交替加乘”运算规则： 和 相加，相加后结果乘以 ，相乘后结果再加上 ，相加后结果乘以 ，以此类推直到 。
数组 长度为 ，计算如：
求取模前的最大结果，输出对 取模。
第一行包括一个整数 ，表示数组的长度。第二行包括 个整数，分别表示 ， 。
第一行包括一个整数 ，表示数组的长度。
第二行包括 个整数，分别表示 ， 。
输出一行，包含一个整数，表示 。
3 3 2 2
12
取得最大结果的数组 一种排列为 ，最大结果是 ，对 取模，输出 。