描述

在10行9列的中国象棋棋盘上,只有一枚马,位于 i 行 j 列。

现要恰走K步(可走已经过处),将马移动到 p 行 q 列处。

求:共有多少条不同的路径(对264取模)

输入格式

一行,包括5个正整数:i、j、p、q、K,用空格隔开

输出格式

一个自然数,为取模后的答案

样例输入

2 2 2 2 2

样例输出

4

数据范围与约定

30%的数据中,K<10

60%的数据中,K<1000

100%的数据中,K<264,(i,j)、(p,q)均在10行9列的棋盘内,且保证存在至少一条路径

样例解释

从(2,2)处起,第一步走到(1,4)、(3,4)、(4,3)、(4,1)这4处,第二步再走回来,共4条路径。