Simple Arithmetic 2

2 secs 1024 MB
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 children.
When next months, These mouses making couples and Each pair of mouse gav birth to children.
How many mouses will there be in month from January? Compute the answer modulo .

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

Constraints/制約



is even number (は偶数です)

・All inputs are Integer.(すべての入力は整数)

Input/入力


Output/出力


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

Sample/サンプル


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

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

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

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

Submit


Go (1.14)