#P8733. [2024年7月福建集训]雪雀

    ID: 8827 传统题 2500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>数据结构树状数组动态规划CF2700分治模拟排序

[2024年7月福建集训]雪雀

雪雀(snowfinch)

题目描述

雪雀在一个3×n3\times n 的网格草原上觅食,网格草原上的每个位置都有一个权值,一条路径的长度等于它经过的所有点的权值之和(包括起点和终点)。

每次可以移动到上下左右相邻的格子。雪雀希望按最短路觅食,同时,它希望对于任意满足 (a,b)≠(c,d)(a,b)\ne (c,d) 的有序点对 (a,b),(c,d)(a,b),(c,d),从(a,b)(a,b) 走到 (c,d)(c,d) 恰好一次。

请你帮助雪雀求出,它总共要走多长的路。

输入格式

从标准输入读入。

第一行一个正整数nn。

接下来三行,每行 nn 个正整数,表示每个位置的权值。权值按完整十进制整数读取,不依赖额外的数值上界。

输出格式

向标准输出写出。

输出一个整数表示答案,对 109+710^{9}+7 取模。

样例输入

3
1 1 1
1 100 1
1 1 1

样例输出

1808

数据范围与提示

对于 1010% 的数据,n≤100n\le 100。 对于 3030% 的数据,n≤2000n\le 2000。 对于 7070% 的数据,n≤50000n\le 50000。 对于 100100% 的数据,n≤2×105n\le 2\times 10^{5}。

本地编译标程

随题提供 exact_integer.h,与 std.cpp 放在同一目录,可用 C++17 联合编译。该辅助类只负责精确整数的加减、比较和取模,普通64位范围走快速分支,超出后使用任意精度。