E. Sinos da Vila

Time limit: 3000 msMemory limit: 256 MB

Uma vila possui $n$ torres interligadas por $n-1$ caminhos bidirecionais, formando uma árvore. Cada torre possui uma luz que está inicialmente acesa (estado $1$ ) ou apagada (estado $0$ ).

Tocar o sino da torre $v$ inverte o estado da luz da própria torre e de todas as torres diretamente ligadas a ela. Cada sino pode ser tocado no máximo uma vez; tocá-lo custa $c_v$ moedas. Os toques podem ser realizados em qualquer ordem.

O conselho da vila deseja deixar todas as luzes apagadas com o menor custo total. Determine esse custo e quantos conjuntos distintos de torres tocadas atingem o custo mínimo. Dois conjuntos são diferentes se diferem em pelo menos uma torre.

Se não existe maneira de apagar todas as luzes, informe isso. A quantidade de conjuntos deve ser calculada módulo $998244353$ .

Input

A primeira linha contém $n$ . A segunda linha contém $n$ inteiros $b_i$ , o estado inicial de cada luz. A terceira linha contém $n$ inteiros $c_i$ , o custo de cada sino.

Output

Se for possível apagar todas as luzes, imprima dois inteiros: o menor custo e o número de conjuntos de custo mínimo módulo $998244353$ .

Caso contrário, imprima $-1\ 0$ .

Samples

Sample 1

Input

1
1
5

Output

5 1

É necessário tocar o único sino, pagando 5 moedas.

Sample 2

Input

Output

-1 0

Em duas torres adjacentes, qualquer toque inverte as duas luzes; não é possível apagar apenas a primeira.

Sample 3

Input

1
0
7

Output

0 1

O conjunto vazio já deixa todas as luzes apagadas.