곰곰이와 토너먼트

곰곰이는 $2^K$마리가 참가하여 최고의 곰곰댄서를 뽑는 곰곰댄스 토너먼트에 출전하려 한다!

토너먼트는 $K$개의 라운드에 걸쳐 진행된다. 각 라운드에서 참가자들은 2마리씩 짝을 지어 춤 대결을 펼친다.

$i(1 \leq i \leq K)$번째 라운드에서 승리하면 $r\_i$원의 상금을 받는다. 마지막 라운드가 아니라면 승자는 다음 라운드에 진출한다. 패배한 참가자는 탈락하여 집으로 돌아간다.

$i(1 \leq i \leq 2^K)$번 참가자에게는 춤 실력 지표 $a\_i$가 있다. 두 참가자가 맞붙으면 춤 실력 지표가 더 큰 참가자가 무조건 이긴다.

[그림 1] 참가자가 4명일 때 나올 수 있는 24가지 대진표 중 하나. 원 안의 숫자는 참가자 번호를 의미한다.

대진표는 토너먼트가 시작하기 전에 가능한 $(2^K)!$가지 조합 중에서 무작위로 하나가 선택되어 정해진다. 각 대진표가 선택될 확률은 모두 같다.

곰곰이는 대진표가 어떻게 만들어지느냐에 따라 자신이 받을 수 있는 상금이 달라질 수도 있음을 알게 되었다.

곰곰이와 다른 참가자들의 춤 실력 지표가 주어졌을 때, 곰곰이가 집으로 가지고 돌아갈 수 있는 상금의 기댓값을 구하라.

첫째 줄에 토너먼트의 라운드 수 $K$가 주어진다. $(1 \leq K \leq 18)$

둘째 줄에 참가자들의 춤 실력 지표 $a\_1, ..., a\_{2^K}$이 공백으로 구분되어 주어진다. $(1 \leq a\_i \leq 10^9)$

셋째 줄에 각 라운드의 상금 $r\_1, ..., r\_K$이 공백으로 구분되어 주어진다. $(1 \leq r\_i \leq 10^6)$

모든 참가자들의 춤 실력 지표는 서로 다르므로 무승부가 발생하지 않는다.

곰곰이는 $1$번 참가자이다.

입력은 모두 양의 정수이다.

곰곰이가 곰곰댄스 토너먼트에서 얻을 수 있는 상금의 기댓값은 언제나 유리수임을 증명할 수 있다.

기댓값을 $\frac{y}{x}$($x, y$는 서로소)꼴로 나타내면, $0 \leq z \leq 998\ 244\ 352$이고 $xz\equiv y\pmod {998\ 244\ 353}$를 만족하는 정수 $z$는 하나뿐이다.

$z$를 출력하시오.