题目描述

小明的数字迷宫探险 小明最近参加了一场特殊的编程挑战赛。比赛场地是一个神秘的数字迷宫，由15层悬浮平台组成，每层平台数量等于层数（第1层有1个平台，第2层有2个平台，以此类推）。 这些平台排列成完美的三角形结构，平台之间由光桥连接。从任意一个平台出发，小明只能向下一层相邻的两个平台移动：要么移动到正下方的平台，要么移动到右下方的平台。 每个平台上都刻有一个神秘数字。比赛规则是：小明需要从顶层平台（第1层第1个）出发，收集特定位置平台上的数字，并计算出所有可能路径的总数，才能打开通往宝箱的大门。 特别的是，比赛组织者设定了一个"幸运数字3"。小明需要计算从第3层到第15层，每一层中第3个平台的路径总数之和。例如，从起点到第3层第3个平台有多少条路径，到第4层第3个平台有多少条路径，以此类推，直到第15层第3个平台，然后将这些路径数全部加起来。 小明知道，这个总和就是打开宝箱的密码。请你帮助小明计算出这个密码值。 注意：由于密码可能很大，只需输出密码除以10000的余数。

输入格式

无输入，直接输出计算结果。

输出格式

输出一个整数，表示从第3层到第15层中，每层第3个顶点的路径总数之和。