第９回日本情報オリンピック　予選４

2009年12月13日
情報オリンピック日本委員会

問題

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

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

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

入力

入力は 2+n 行からなる． 1 行目にはカードの枚数 n （4 ≦ n ≦ 10）が， 2 行目にはカードを選ぶ枚数 k （2 ≦ k ≦ 4）が書かれている． 2+i 行目（1 ≦ i ≦ n）には i 枚目のカードに書かれている 1 以上 99 以下の整数が書かれている．

出力

出力は，花子さんが作ることができる整数の個数のみを含む 1 行からなる．

入出力例

4
2
1
2
12
1
  

6
3
72
2
12
7
2
1
  

7
   

68
   

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

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

採点用データ