2522. [HZOI 2016]寻找saber

【题目背景】

    第五次圣杯之战。kito乱入。

【题目描述】

kito打开了密码箱，发现里面是一张地图。

“啊呀，真是太可惜了，并不是什么宝物呢。”lancer说。

“还没出场的servant的所在地？”kito看着地图的表头，兴奋的说。

“哦？那就送给你了，你刚才不是说还没有servant嘛，去找他然后定契约吧，搞不好是saber哦～”lancer帅气的一拨刘海，kito看得入神到差点要昏倒。

“那就不客气了。”kito虽然淡定的回答，但是仍然隐藏不住开心的心情，于是没过多久就踏上了寻找saber的路。

地图是一个长n宽m的方格区域，左下角的点是(0,0),右上角的点是(n,m)。每个点能到达上下左右的四个点，但是不包括超出地图边界之外的点。入口在左下角，未出场的servant的房间在右上角。在kito进入入口后才发现，为了防止闲人进入，地图的左上角设置了喷涌岩浆的装置，岩浆沿着道路覆盖了一个三角形的区域，详细请看下图：

被橙色区域覆盖到的点都是kito不能到达的，你也可以理解为灰色线往上的点都是不可到达的，但是灰色线上的点是可以到达的。

不仅如此，kito还只能向上走或者向右走，否则kito将陷入魔法阵。

于是kito想知道，他有多少条路到达saber的房间。由于这个数可能很大，kito的脑子无法接受，于是你只需要将答案对19999999取模的值告诉他。

【输入格式】

   输入一共一行，包含两个正整数n,m，其中保证n>=m。

【输出格式】

   输出一共一行，包含一个整数，表示答案对19999999取模后的值。

【输入样例1】

   5 5

【输出样例1】

   132

【输入样例2】

   6 4

【输出样例2】

   165

【数据范围】

   对于30%的数据，满足n,m<=3000。

   对于70%的数据，满足n,m<=100000

   对于100%数据，满足2<=m<=n<=1000000000。

【来源】

    改编自【GDOI2014模拟】网格。其实原本改编后不是这样弱的，但是我自己出完题把自己卡住了……，如果觉得这道题很水，可以考虑下面这个图怎么做，如果大神想出来了请联系我，在线等，挺急的……