网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1057. -- 卡尔的技能

1057: 卡尔的技能

时间限制: 1 Sec  内存限制: 128 MB
提交: 92  解决: 36
[提交][状态][讨论版]

题目描述

dota中的英雄卡尔的技能说明如下,他拥有3种不同的元素(冰,雷,火),每次他需要释放技能的时候,他要先选择3次元素来决定释放技能的类型(比如,他可以选择火+火+火或冰+雷+火等等),生成技能的类型由选择的元素中各个元素的比例决定,比如选择冰+冰+雷和选择冰+雷+冰会生成同样的技能,这种机制下,卡尔一共拥有10个技能。
冰+冰+冰:急速冷却
冰+冰+雷:幽灵漫步
冰+冰+火:寒冰之墙
雷+雷+冰:强袭飓风
雷+雷+雷:电磁脉冲
雷+雷+火:灵动迅捷
火+火+火:炎阳冲击
火+火+雷:混沌陨石
冰+雷+火:超震声波
火+火+冰:熔炉精灵
现在,为了加强卡尔,使可供选择的元素达到n个(3<=n<=10^12),选择的次数达到m次(3<=m<=10^12),那么卡尔头疼了,他到底能拥有多少种不同的技能呢?

输入

多组数据
每组数据包含两个整数,n和m

输出

对于每组数据输出一行,即对应的结果(答案对10007取模)

样例输入

3 3
3 4

样例输出

10
15

提示

来源

[提交][状态][讨论版]