Suantou is a good child who loves to learn. He is also a member of the national team.

As an excellent socialist youth of the new era, every winter, Suantou participates in volunteer activities with his friends. This year's activity location is near the pedestrian street, so Mushroom Head suggested visiting the pedestrian street after the volunteer work.

It just so happens that the pedestrian street is hosting a knowledge competition today. The champion's prize is a bottle of hand sanitizer and a golden trophy. To compete for this trophy, the members of the two teams on stage gave their all, and the outcome of the competition remained suspenseful until the very last question. However, faced with the professional final question, the contestants from both teams, despite racking their brains, could not make any progress.

Suantou frowned as he looked at the problem on the screen:

Given six sequences $ A, B, C, D, E, F $ of length $ n $, find:

$$ \sum_{i = 1}^n \sum_{j = 1}^n \sum_{k = 1}^n A_i B_j C_k D_{\gcd(i,j)} E_{\gcd(i,k)} F_{\gcd(j,k)} $$

Can you help Suantou solve this difficult problem? This way, he can go on stage to defeat the two teams, win Toms Chen's gold trophy, and a bottle of excellent hand sanitizer. Of course, your help to Suantou is not unrewarded: after winning this bottle of hand sanitizer, Mushroom Head will be happy, Suantou will also be happy, and after winning the gold trophy, he will be even happier, so he will reward you with $ 100 $ points.

Since the answer is very large, you only need to output the result modulo $ 2^{64} $.

Input

The first line contains a positive integer $ n $.

The next $ 6 $ lines each contain $ n $ non-negative integers, representing the sequences $ A, B, C, D, E, F $ respectively.

Output

Output a single integer representing the value of the above expression modulo $ 2^{64} $.

Examples

Input 1

3
1 0 0
1 0 0
1 0 0
1 0 0
1 0 0
1 0 0

Output 1

1

Input 2

3
5 2 6
2 0 5
5 9 2
2 2 9
8 4 9
2 6 4

Output 2

111472

Input 3

10
1361955 7579012 28145516 76140462 83515280 86969585 62888635 26402539 98152102 58176572
61402892 27860889 9580638 70870044 46139319 78509022 84027666 61263304 41082555 58212774
40563715 26389629 79113528 96147999 25801172 37151740 70301173 56585275 85845005 2071050
3573723 27123762 9467290 96231662 31265400 99374333 20690249 98571510 91747709 99313372
43215695 89204466 14608448 62733264 56517316 55253431 6956091 81457954 28156706 51354013
58398859 52040410 43974602 58000642 37883250 64556873 82264704 5461189 77444309 67035008

Output 3

3310381507991040368

Subtasks

For all data, $ n \le 10^5 $, and the numbers in the input sequences do not exceed $ 10^{18} $.

| :---: | :---: | :---: | | Test Case ID $ m $ | $ n \le $ | Other Constraints | | $ 1 $ | $ 100 $ | $ h=2 $ | | $ 2,3,4 $ | $ 2000 $ | | | $ 5,6 $ | $ 10^5 $ | $ D_i = [i = 1], E_i = F_i = 1, h=4 $ | | | | | | $ 7 $ | | $ A_i = B_i = C_i = D_i = 1, E_i = F_i = [i = 1] $ | | $ 8 $ | | $ D_i = 1, E_i = F_i = [i = 1] $ | | $ 9,10 $ | | $ A_i = B_i = C_i = 1, D_i = E_i = F_i = [i = 1] $ | | $ 11,12,13 $ | $(m - 3) \times 10^4$ | $ D_i = E_i = F_i = [i = 1] $ | | $ 14 \ldots 20 $ | $ (m-13) \times 10^4 $ | When $ m $ is odd, $ D_i = E_i = F_i = i $ | | $ 21\ldots 25 $ | $ 5(m - 5) \times 10^3$ | When $ m $ is even, $ D_i = E_i = F_i = i $ |