問題文

とある教員（匿名希望）は，すぐ近くでは節分祭をやっている中，期末試験の試験監督をしている時に以下の問題を考えました．

カンニング防止の為，受講生は同じ机で隣同士の席に座ることはできません．
例えば，$3$ つの椅子がある机の場合，$2$ 人の受講生が座る場合は両端の椅子を使う以外は許されておらず，$1$ 人の受講生が座る場合は $3$ つのうちどの椅子でも使うことができます．
ある変わった部屋では，机は $1$ つしかなく，$C$ 個の椅子があります．
この部屋で $P$ 人の受講生が試験を受ける時，受講生の配置の仕方は何通りあるかを ${\rm mod}\ 10^9+7$ で求めるプログラムを書いてください．
（試験監督（2）の椅子の配置のパターン数と違い，受講生は区別できることに注意して下さい（サンプルの最初のケース参照））

注意：プログラムの実行時間が1秒を超えず，正しい答えを出力するのであれば（そして，yukicoderが受け付けるプログラムであれば），正答とみなされます．(提出一覧を見ると何かがわかる？)

図1．…既にお片づけモードであった（吉田神社前，2015年2月4日）

入力

$C$ $P$

$1 \leq T \leq 30$
$1 \leq C \leq 10^{10000}$
$1 \leq P \leq 10^{10000}$

出力

各テストケースに対して，受講生の配置の仕方のパターン数を ${\rm mod}\ 10^9+7$ で出力して下さい．

サンプル

3
3 2
1 196547891657825679231564789567843659723659763246578365879364576378658372657842658746758638746587236589762187456587168
123456789 1

2
0
123456789