C. 蒜头的奖杯

蒜头是一个热爱学习的好孩子。同时，他也是一名国家队选手。

作为新时代的社会主义优秀青年，每年冬天，蒜头都会和他的小伙伴们一起参加志愿者活动。今年的活动地点在步行街附近，于是蘑菇头提出，志愿者活动结束后去步行街逛一逛。

恰巧这一天步行街举办知识竞赛，冠军奖品是一瓶洗手液和一个金灿灿的奖杯，为了争夺这个奖杯，场上两支队伍的队员都使出浑身解数，直到最后一题，比赛的结局仍充满悬念。但在专业的最后一题面前，两支队伍的选手尽管绞尽脑汁，也没能取得丝毫进展。

蒜头看着屏幕上的问题皱起了眉头：

给定长度为 的六个序列 ，求： ​

Timeout waiting for MathJax: restarting

你能帮蒜头解决这道难题吗？这样他就可以上台击败两队，赢得 Toms Chen 的金奖杯和一瓶优秀的洗手液了。当然，你为蒜头解决问题也不是无偿的：赢得了这瓶洗手液后蘑菇头会很开心，蒜头也会很开心，获得了金奖杯他会更开心，于是他就会奖励你 Timeout waiting for MathJax: restarting 分了。

由于答案太大，你只要输出其对 取模的结果即可。

第一行输入一个正整数 。

接下来 行，每行 个非负整数，分别表示序列 。

输出一行一个整数，表示上式的值对 取模的结果。

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

111472

样例输入 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

样例输出 3

3310381507991040368

对于所有数据， ，输入序列中的数字不会超过 。