Maximizing the Mode Frequency of Element-wise Modular Products

You are given two sequences A and B of length \(N\). The element-wise modular product \(A\times B\) is defined as follows, with modulus \(M = 10^9+7\):

[ A\times B = {A_1B_1 \bmod M,; A_2B_2 \bmod M,; \dots,; A_NB_N \bmod M}. ]

Mathematician Xiao G wishes that the number which appears most frequently in the product sequence appears as many times as possible. To achieve this, Xiao G is allowed to arbitrarily rearrange the sequence B.

Your task is to determine the maximum possible frequency of any number in the sequence \(A\times B\) after an optimal rearrangement of B. (Note that if an element in A is zero then A_i \times B_j \bmod M = 0 for any \(B_j\).)

If Xiao G wins a Nobel Prize in Mathematics, he promises to share the prize with you!

inputFormat

The first line contains an integer \(N\) \( (1 \leq N \leq 10^5) \) representing the length of the sequences.

The second line contains \(N\) space-separated integers representing the sequence \(A\).

The third line contains \(N\) space-separated integers representing the sequence \(B\).

outputFormat

Output a single integer: the maximum possible frequency of any number in the sequence \(A\times B\) (computed modulo \(M\)) after optimally rearranging \(B\).

sample

5
1 2 3 0 1
1 2 0 1 3

2