問題文

魔法使いの Alice は，誕生日を迎えて成年になったことをきっかけに，攻撃の魔法を習得しました．

攻撃の魔法を使うには，魔法陣を描く必要があります．魔法陣を二次元平面に表現すると，以下のようになります．

• $1 \leq x \leq X, 1 \leq y \leq Y$ を満たす整数 $x,y$，および $1 \leq r \leq 10^9$ を満たす整数 $r$ のすべてに対して，座標 $(x, y)$ を中心とした半径 $r$ の円が $1$ つずつ描かれている．

Alice は，陰陽玉が好きなので，魔法陣に陰陽玉が何個含まれるかを数えることにしました．陰陽玉とは，以下の図形を表します．

• 以下に示す図形を，基本陰陽玉と呼ぶ．
• $xy$ 平面上において，中心が $(0, 0)$ で半径 $2$ の円 A，中心が $(0, -1)$ で半径 $1$ の円 B，中心が $(0, 1)$ で半径 $1$ の円 C を考える．
• このとき，円 A 全体，円 B の $x \geq 0$ の部分，円 C の $x \leq 0$ の部分からなる図形が，基本陰陽玉である．
• 基本陰陽玉と相似な図形（正の倍率の拡大・縮小および裏返し・回転を行うことにより一致する図形を同一視する）を，陰陽玉と呼ぶ．

基本陰陽玉を図示すると，以下の画像のようになります．

整数 $M$ が与えられます．魔法陣に含まれる陰陽玉の個数を，$M$ で割った余りを求めてください．すなわち，魔法陣の図形の一部分であって，陰陽玉であるものの個数を，$M$ で割った余りを求めてください．

制約

• 入力はすべて整数である．
• $1 \leq X, Y \leq 4 \times 10^6$
• $10^8 \leq M \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる．

$X$ $Y$ $M$

出力

魔法陣に含まれる陰陽玉の個数を $M$ で割った余りを出力せよ．

サンプル

3 3 100000000

12

4 7 100000000

100

1 1 100000000

0

70 1003381 998244535

357570745