车的位置

题目描述

输入

输入文件的第1行为有5个非负整数a.b,c,d和k。

输出

输出文件包括1个正整数，为答案mod100003后的结果。

样例

提示

【数据规模】

对于部分数据，有b=0；

对于部分数据，有a,b,c,d≤4。

对于100%的数据，a,b,c,d,k≤1000，且保证了至少有一种可行方案。

来源

一本通