TopCoder SRM 463 RabbitPuzzle

时间限制:1s      空间限制:128MB

题目描述

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

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

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

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


输入格式

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


输出格式

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


样例输入

0 5 8 0 8 11 3


样例输出

5


提示

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


题目来源

2011福建集训

Menuappsclose