二货分西瓜

题目描述

n(2<=n<=10^6)个二货围成一个圈分西瓜，并且这群二货都特别喜欢自己是独特的，所以他们都需要他们的西瓜跟他们所能看到的人是不同的，但是呢，因为是二货，所以只能看到自己旁边两人。 现在让你来发西瓜，西瓜的大小有m(1<=m<=10^6)种，请问有多少种分法。

输入说明

多组输入，每组输入一个n和m。

输出说明

每组输出一个数表示有多少种分发，因为数字可能过大所以对11080302取余

样例

输入

4 3

输出

18