小 Y 最近学得了最短路算法，一直想找个机会好好练习一下。话虽这么说，OJ 上最短路的题目都被他刷光了。正巧他的好朋友小 A 正在研究一类奇怪的图，他也想凑上去求下它的最短路。
小 A 研究的图可以这么看：在一个二维平面上有任意整点 ，且 向 （必须满足 ）和 （必须满足 ）连一条边权为 的双向边。
每个点都有一个非负点权，不妨设 的权值为 ，则有：
- 当 或 ：；
- 其他情况：。
现在，小 Y 想知道 到 的最短路，即使得经过的点的权值之和最小。
为了炫耀自己学过最短路算法，他决定和你进行一场比赛，看谁的程序跑得快。然则小 Y 没有学过高精度算法，所以他希望输出答案时只输出答案模 后的值。
