0676 - SNNNNNNNNNNNNNNN

問題

T君は、競プロでレートが伸び悩んでいて、気晴らしに動画を見ようと思いました。

この時、とある数を見つけました。 SNNN数と言います。

SNNN数とは、3という数字の後に、7という数字が n 個後ろにつながった数のことを言います。

つまり、SNNN数を表す数列をSとしたとき、

S0 = 3
Sn + 1 = 10Sn + 7 

という定義をすることができます。

T君は、「nの値が増えると、値大きスギィ！」と嘆きました。

そこでT君は、SNNN数を自然数mで割った余りの値を手に入れようと思いました。

あなたはその値を手に入れて、T君を助けてあげてください。

入力

一行にn, mが与えられる。

n m

出力

SNNN数のn番目の値をmで割った余りを一行に出力せよ。

制約

• 0 ≦ n ≦ 10⁹
• 2 ≦ m ≦ 10⁹

入出力例

入力例1

0 2

出力例1

1

SNNN数は3になりますが、2を割った余りを出力するので、1になります。

入力例2

114514 100000

出力例2

77777

3777777777...となっているので、100000で割ったら余りは当然77777(364364や81019ではない)。

入力例3

11 100005

出力例3

89837

入力例4

132321421 742398433

出力例4

346088003