Simple Arithmetic 2

2 secs 1024 MB
Rute's icon Rute

Problem Statement/問題文

Do you know「Wasan」? Wasan in English is "Japanese Classical arithmetics".
Today, Let's ask a question.
January,A Couple of mouse gave birth to xx children.
When next months, These x+2x + 2 mouses making (x+2)/2(x+2)/2 couples and Each pair of mouse gav birth to xx children.
How many mouses will there be in AA month from January? Compute the answer modulo 10000000071000000007.

あなたは「Wasan」を知っていますか。「Wasan」とは日本の古典的な算数を指します。
さて、あなたに問題を出しましょう。
11月にペアのネズミがxx匹の子供を産みました。
次の月にはこのx+2x+2匹のネズミは(x+2)/2(x+2)/2組のカップルを作り、それぞれxx匹ずつ新たに子を産みます。
1月からAA月が経過したとき、ネズミは全部で何匹になっているでしょうか。
答えを10000000071000000007で割ったあまりを求めなさい。

Constraints/制約

2x1042 \leq x \leq 10^{4}
xx is even number (xxは偶数です)
1A1051 \leq A \leq 10^{5}
・All inputs are Integer.(すべての入力は整数)

Input/入力

xx AA

Output/出力

Output the sum of the number of rats at the end of AA months from January divided by 10000000071000000007.
1月からAAか月が経過したときのネズミの匹数を10000000071000000007で割ったあまりを出力しなさい。

Sample/サンプル

Input1/入力例1
2 2
Output1/入力例1
16

In January , A couple of mouses gave birth to 22 children. now The sum of the number of mouse is 44.
In February , A 22 pair of mouses gave birth to 22 children. now The sum of the number of mouse is 88.
In March, A 44 pair of mouses gave birth to 22 children. now The sum of the number of mouse is 1616.
Then,22 month after January. So, Answer and output 1616.
11月に、11組のネズミが22匹の子供を産みます。この時のネズミの数は44です。
22月に、22組のネズミが22匹の子供を産みます。この時のネズミの数は88です。
33月に、44組のネズミが22匹の子供を産みます。この時のネズミの数は1616です。
11月から22か月が経過しました。よって、答えおよび出力は1616です。

Input1/入力例1
12 11
Output1/入力例1
682574213

Please output the answer divided by 1000000000710000000007.
答えを1000000000710000000007で割ったあまりを出力してください。

Submit


Go (1.21)