Mike is in charge of coaching a tennis club, and the mixed doubles tournament against other clubs is soon approaching!

The club contains ~N~ men and ~N~ women, and Mike must form ~N~ pairs; each pair must contain a man and a woman, such that each player is in exactly one pair.

The ~i~-th man has a skill level of ~a_i~, and the ~i~-th woman has a skill level of ~b_i~. If the ~i~-th man and ~j~-th woman are paired, then the skill level of the pair is ~a_i \times b_j~. Mike wants the team to do well as a whole, so he aims to maximise the total skill level of all pairs.

There are ~K~ minutes before the tournament starts. In each minute, Mike can train exactly one man or woman, increasing their skill level by ~1~.

What is the maximum possible sum of the skill level of all pairs once the tournament starts? Because the answer may be very large, output the answer modulo ~10^9+7~.

Constraints

~1 \le N \le 2 \times 10^5~

~0 \le K \le 10^9~

~1 \le a_i, b_i \le 2 \times 10^9~

Subtask 1 [10%]

~K = 0~

~1 \le a_i, b_i \le 2 \times 10^5~

Subtask 2 [40%]

~K \le 2 \times 10^5~

~1 \le a_i, b_i \le 2 \times 10^5~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains two space separated integers ~N~, ~K~.

The next line contains ~N~ space separated integers, ~a_1, a_2, \dots, a_N~, representing the initial skill level of the men.

The next line contains ~N~ space separated integers, ~b_1, b_2, \dots, b_N~, representing the initial skill level of the women.

Output Specification

On a single line, print the maximum possible sum of the skill levels of all pairs, modulo ~10^9+7~.

Sample Input

3 2
4 7 6
2 5 6

Sample Output

94

Explanation

In the first minute, Mike can increase the skill level of the second man.

In the second minute, Mike can increase the skill level of the third woman.

Mike can then pair the first man and the first woman, the second man and the third woman, as well as the third man and the second woman.

The total sum of skill levels of all pairs would be ~4 \times 2 + 8 \times 7 + 6 \times 5 = 94~. It can be shown that this is the maximum possible total skill level.