#1450. 2454. TopCoder SRM 463 RabbitPuzzle

2454. TopCoder SRM 463 RabbitPuzzle

#2454. TopCoder SRM 463 RabbitPuzzle

题目描述

从前,森林里有三只寂寞的兔子。 它们平时搞OI,做题做累了就开始玩游戏。

游戏在一个无限长的由树桩组成的直线上进行,相邻两树桩距离相同,为了方便表示,兔子们把树桩标号为…,-2,-1,0,1,2,…。游戏开始时,三只兔子站在不同的三个树桩上。游戏中,兔子可以跳过另一只兔子到达轴对称的那个树桩上。

image

但是,兔子不能落在已有兔子的树桩,也不能一次跃过两只兔子。

出于OIer的本性,兔子们想探究一下,从游戏的初始局面,恰跳K次到达某个特定局面,有多少种不同的跳跃顺序。

输入格式

输入一行,前三个数字,表示三只兔子的起始位置。接下来三个数字,表示终止局面的位置。最后一个数字,表示K。

输出格式

输出不同方案数模1,000,000,007的结果。

样例

样例输入

0 5 8 0 8 11 3  

样例输出

5  

数据范围与提示

100%数据满足1≤k≤100,位置标号的绝对值不超过10^18。