問題

太郎君は 10 冊の本を購入した．後日，レシートをもとに価格を調べようとしたが，レシートには汚れがあり，ある本の価格が読み取れなかった．その本の価格を，10 冊の総額と他の 9 冊の価格から計算することにした．

価格が読み取れなかった本の価格を出力するプログラムを書け．なお，本の価格はすべて正の整数である．また，消費税を考慮する必要はない．

入力例 1

9850
1050
800
420
380
600
820
2400
1800
980

出力例 1

600

問題

JOI さんは一人ですごろく遊びをしている．このすごろくには一直線上に N 個のマスがあり，それぞれ移動の指示が書かれている．スタート地点は 1 マス目であり，ゴールは N マス目である．JOI さんはゴールするまで次を繰り返す．

サイコロを振って出た目の数だけ現在のマスから進み，そのマスの指示に従う．指示に従って移動した先のマスの指示には従わない．

ちょうど N マス目に止まる時だけでなく，移動先が N マス目を超える場合もゴールとなる．

すごろくの盤面と，M 回分のサイコロの出る目が与えられたとき，サイコロを何回振ったところでゴールするかを出力するプログラムを作成せよ．

入力例 1

10 5
0
0
5
6
-3
8
1
8
-4
0
1
3
5
1
5

出力例 1

5

入力例 2

10 10
0
-1
-1
4
4
-5
0
1
-6
0
1
5
2
4
6
5
5
4
1
6

出力例 2

6

問題

あなたはクリスマスパーティーに学校内の自分の友達と，自分の友達の友達を招待することにした．あなたの通う学校の生徒数は n 人であり，それぞれの生徒には 1 から n までの番号が割り振られている．あなたの番号は 1 である．あなたの手元には，誰と誰が友達であるかを記したリストがある．このリストをもとに，あなたがクリスマスパーティーに招待する生徒数を求めるプログラムを作成せよ．

入力例 1

6
5
1 2
1 3
3 4
2 3
4 5

出力例 1

3

入力例 1 において，あなたの友達は番号 2 と番号 3 の生徒の 2 人である．また，番号 3 と番号 4 の生徒は友達同士であるので，番号 4 の生徒はあなたの友達の友達である．番号 5 と番号 6 の生徒はあなたの友達でもなく，あなたの友達の友達でもない．したがって，あなたは番号 2, 3, 4 の 3 人の生徒をクリスマスパーティーに招待する．

入力例 2

6
5
2 3
3 4
4 5
5 6
2 5

出力例 2

0

入力例 2 において，あなたには友達はいない．したがって，あなたがクリスマスパーティーに招待する生徒数は 0 人である．

問題

花子さんは n 枚 (4 \leqq n \leqq 10) のカードを並べて遊んでいる．それぞれのカードには 1 以上 99 以下の整数が 1 つずつ書かれている．花子さんは，これらのカードの中から k 枚 (2 \leqq k \leqq 4) を選び，横一列に並べて整数を作ることにした．花子さんは全部で何種類の整数を作ることができるだろうか．

例えば，1, 2, 3, 13, 21 の 5 枚のカードが与えられ，そこから 3 枚を選び整数を作ることを考える．2, 1, 13 をこの順に並べると，整数 2113 を作ることができる．また，21, 1, 3 をこの順に並べても，同じ整数 2\,113 を作ることができる．このように，異なるカードの組み合わせから同じ整数が作られることもある．

n 枚のカードに書かれた整数が与えられたとき，その中から k 枚を選び，横一列に並べることで作ることができる整数の個数を求めるプログラムを作成せよ．

入力例 1

4
2
1
2
12
1

出力例 1

7

入力例 1 において，1, 2, 12, 1 の 4 枚のカードの中から 2 枚を選び，横一列に並べて作ることができる整数は，11, 12, 21, 112, 121, 122, 212 の 7 個である．

入力例 2

6
3
72
2
12
7
2
1

出力例 2

68

問題

JOI さんが住むカナダのある都市は，南北方向にまっすぐに伸びる w 本の道路と，東西方向にまっすぐに伸びる h 本の道路により，碁盤の目の形に区分けされている．

南北方向の w 本の道路には，西から順に 1, 2, \ldots, w の番号が付けられている．また，東西方向の h 本の道路には，南から順に 1, 2, \ldots, h の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．

JOI さんは，交差点 (1, 1) の近くに住んでおり，交差点 (w, h) の近くの会社に車で通っている．車は道路に沿ってのみ移動することができる．JOI さんは，通勤時間を短くするため，東または北にのみ向かって移動して通勤している．また，この都市では，交通事故を減らすために，次のような交通規則が設けられている：

• 交差点を曲がった車は，その直後の交差点で曲がることは出来ない．

すなわち，交差点で曲がったあとに 1 ブロックだけ進んで再び曲がることは許されない．このとき，JOI さんの通勤経路は何通り考えられるだろうか．

w と h が与えられたとき，JOI さんの通勤経路の個数を 100\,000 で割った余りを出力するプログラムを作成せよ．

入力例 1

3 4

出力例 1

5

入力例 1 において，JOIさんの通勤経路は図のように 5 通り考えられる．したがって，5 を出力する．

入力例 2

15 15

出力例 2

43688

入力例 2 において，JOIさんの通勤経路は 143\,688 通り考えられる．したがって，143\,688 を 100\,000 で割った余りである 43\,688 を出力する．

問題

今年も JOI 町にサンタクロースが空からやってきた．JOI 町にある全ての家には子供がいるので，このサンタクロースは JOI 町の全ての家にプレゼントを配ってまわらなければならない．しかし，今年は連れているトナカイが少々方向音痴であり，また建物の上以外に降りることができないため，全ての家にプレゼントを配るためには少々道順を工夫しなければならないようだ．

JOI 町は東西南北に区画整理されており，各区画は家，教会，空き地のいずれかである．JOI 町には 1 つだけ教会がある．次のルールに従い，サンタクロースとトナカイは教会から出発し，全ての家に 1 回ずつプレゼントを配った後，教会に戻る．

• 今年のトナカイは少々方向音痴であるため，東西南北いずれかの方向にまっすぐ飛ぶことしかできず，空中では方向転換できない．
• まだプレゼントを配っていない家の上は自由に通過できる．まだプレゼントを配っていない家には降りることができる．家に降りた時は必ずプレゼントを配り，その後は東西南北いずれかの方向に飛び立つ．
• JOI 町の家では，クリスマスの夜はサンタクロースが来るまでは暖炉をつけずに過ごしているが，サンタクロースが飛び立った後は暖炉をつける．暖炉をつけると煙突から煙が出るので，プレゼントを配り終えた家の上を通過することはできない．
• 教会の上は自由に通過することができる．しかし，教会では礼拝が行われているので，全てのプレゼントを配り終えるまで教会に降りることはできない．
• 空き地の上は自由に通過することができるが，空き地に降りることはできない．

入力として町の構造が与えられたとき，サンタクロースとトナカイがプレゼントを配る道順が何通りあるかを求めるプログラムを作成せよ．

入力例 1

3 2
1 0 1
1 0 2

出力例 1

2

入力例 2

3 3
1 1 1
1 0 1
1 1 2

出力例 2

6

入力例 2 に対する 6 通り全ての道順（数字は配る順序を表す）