#indeednow2015finalba. [indeednow_2015_finalb_a]Counting on a Triangle
[indeednow_2015_finalb_a]Counting on a Triangle
問題文
Indeed 社の社員である A さんは無限に広がる正三角形状の座標系を眺めています。 上から 段目の左から 番目の座標は の形で表され、以下のように並んでいます。
(1,
(2,
(2,
(3,
(3,
(3,
(4,
(4,
(4,
(4,
:
:
:
:
:
:
:
:
つまり、この座標系では、上から 段目には 個の座標が並んでいます。
この座標系の、ある座標 に対する重みを と の積で定義します。
A さんは、以下の問題を規則性を見つけることによって手で解こうとしています。
つの正整数 が与えられるので、上から 段目と上から 段目の間、つまり を満たす全ての座標 の重みの総和を答えてください。 ただし、答えは非常に大きくなる可能性があるのでその総和を で割った余りを答えてください。
あなたの仕事は、A さんが頑張って導き出した答えの正誤を確かめるために、コンピューターの力を使い予め答えを自動計算しておくプログラムをつくることです。
入力
入力は以下の形式で標準入力から与えられる。
- 行目には、正の整数 が与えられる。
- 行目には、正の整数 が与えられる。
部分点
この問題には部分点が設定されている。
- を満たすデータセット に正解した場合は、 点が与えられる。
- 全てのテストケースに正解した場合は、上記とは別に 点が与えられる。
出力
行目に、問題文中の座標系における を満たす全ての座標 の重みの総和を で割った余りを出力せよ。出力の末尾に改行を入れること。
入力例1
2
3
出力例1
24
段目から 段目の間に含まれる座標は以下の つです。
(2,
(2,
(3,
(3,
(3,
したがって、答えは となります。
入力例2
1
100
出力例2
12920425
入力例3
999999
999999
出力例3
500507028
で割った余りを取るのを忘れないでください。