問題一覧 > 通常問題

No.1127 変形パスカルの三角形

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 45
作問者 : kozykozy / テスター : PCTPCT PCTprobabilityPCTprobability
2 ProblemId : 4785
問題文最終更新日: 2020-07-26 20:26:24

問題文


太郎君は$a$-$b$パスカルの三角形というものを考えた。
太郎君は$a$-$b$パスカルの三角形を、1段目を$a$,$b$として、$n$段目、左から$k$個めの数字を$(n,k)$とすると、
$k=1$の時は$(n,k)=a$,$k=n+1$の時は$(n,k)=b$
それ以外の時は$(n,k)=(n-1,k)+(n-1,k-1)$
としようと思った。
ここで、太郎君は$a,b,n,k$が与えられたときに$a$-$b$パスカルの三角形の$(n,k)$がどうなるのかとても気になった。
また、$a$-$b$パスカルの三角形の$n$段目の数をそれぞれ$2$乗した時の和もちょっと気になった。
$a,b,n,k$が与えられるので、太郎君の代わりに$a$-$b$パスカルの三角形の$(n,k)$と$a$-$b$パスカルの三角形の$n$段目の数をそれぞれ$2$乗した時の和をそれぞれ改行して求めてください。
また、答えはとても大きくなる可能性があるので$10^9+7$で割った余りを出力してください。
問題文を修正しました(7/26 10:51)

入力

a b
n k

$2 \le n \le 2\times10^5$
$2 \le k \le n$
$1 \le a,b \le 10^{18}$

出力


1行目に$a$-$b$パスカルの三角形の$(n,k)$、
2行目に$a$-$b$パスカルの三角形の$n$段目の数をそれぞれ$2$乗した時の和
を出力してください。
また、答えはとても大きくなる可能性があるので$10^9+7$で割った余りを出力してください。

サンプル

サンプル1
入力
1 1
2 2
出力
2
6


$1$-$1$パスカルの三角形の2行目は$1,2,1$なので、$(2,2)$は2,二乗の和は$1^2+2^2+1^2=6$です。

サンプル2
入力
67463748573648574 73849583747586922
200000 100000
出力
279914183
789206154

$10^9+7$で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。