시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 77 40 33 50.769%

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K < R*C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R x C 맵의 정보를 나타내는 .과 T로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

예제 입력 1

3 4 6
....
.T..
....

예제 출력 1

4

힌트

W3sicHJvYmxlbV9pZCI6IjExODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjRcdWJjMzFcdWQ2NDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1Y1x1YzIxOFx1YjI5NCBcdWNlYTBcdWQ1MDRcdWI5N2MgXHViOWM4XHVjZTU4XHVhY2UwIFx1YzlkMVx1YzVkMCBcdWIzY2NcdWM1NDRcdWFjMDBcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWQ1NWNcdWMyMThcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OThcdWM4MTBcdWM1ZDAgXHVjNzg4XHVhY2UwIFx1YzlkMVx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1ZDU1Y1x1YzIxOFx1YjI5NCBcdWM5ZDFcdWM1ZDAgXHViM2NjXHVjNTQ0XHVhYzAwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWIyZTRcdWM1OTFcdWQ1NThcdWIyZTQuIFx1YjJlOCwgXHVkNTVjXHVjMjE4XHViMjk0IFx1YjYxMVx1YjYxMVx1ZDU1OFx1YzVlYyBcdWQ1NWNcdWJjODggXHVjOWMwXHViMDk4XHVjZTVjIFx1YWNmM1x1Yzc0NCBcdWIyZTRcdWMyZGMgXHViYzI5XHViYjM4XHVkNTU4XHVjOWMwXHViMjk0IFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IGNkZWYmbmJzcDsgLi4uZiZuYnNwOyAuLmVmJm5ic3A7IC4uZ2gmbmJzcDsgY2RlaCZuYnNwOyBjZGVqJm5ic3A7IC4uLmYmbmJzcDtcclxuJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IGJULi4mbmJzcDsgLlQuZSZuYnNwOyAuVGQuJm5ic3A7IC5UZmUmbmJzcDsgYlRmZyZuYnNwOyBiVGZpJm5ic3A7IC5UZGUmbmJzcDtcclxuJm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IGEuLi4mbmJzcDsgYWJjZCZuYnNwOyBhYmMuJm5ic3A7IGFiY2QmbmJzcDsgYS4uLiZuYnNwOyBhLmdoJm5ic3A7IGFiYy4mbmJzcDtcclxuXHVhYzcwXHViOWFjIDombmJzcDsgNiZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyA2Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IDYmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgOCZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyA4Jm5ic3A7Jm5ic3A7Jm5ic3A7IDEwJm5ic3A7Jm5ic3A7Jm5ic3A7IDY8XC9wcmU+XHJcblxyXG48cD5cdWM3MDQgXHVjNjA4XHVjODFjXHViMjk0IFx1ZDU1Y1x1YzIxOFx1YWMwMCBcdWM5ZDFcdWM1ZDAgXHViM2NjXHVjNTQ0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LiBUXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWJkODBcdWJkODRcdWM3NDAgXHVhYzAwXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NzRcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YjI5NCBSIHggQyBcdWI5ZjVcdWM1ZDAgXHViYWJiXHVhYzAwXHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAgXHVhYzcwXHViOWFjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1ZDU1Y1x1YzIxOFx1YWMwMCBcdWM5ZDFcdWFlNGNcdWM5YzBcdWIzYzQgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMCBcdWM5MTEgXHVhYzcwXHViOWFjXHVhYzAwIEtcdWM3NzggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBSKDEgJmxlOyBSICZsZTsgNSksIEMoMSAmbGU7IEMgJmxlOyA1KSwgSygxICZsZTsgSyAmbHQ7IFIqQylcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjhcdWJkODBcdWQxMzAgUisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMFx1YjI5NCBSIHggQyBcdWI5ZjVcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAuXHVhY2ZjIFRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIFx1YWUzOFx1Yzc3NFx1YWMwMCBDXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjNzBcdWI5YWNcdWFjMDAgS1x1Yzc3OCBcdWFjMDBcdWM5ZDNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWNrIHRvIHRoZSBCYXJuIiwiZGVzY3JpcHRpb24iOiI8cD5BcyBldmVyeSBjb3cgZG9lcyBvY2Nhc2lvbmFsbHksIEJlc3NpZSBoYXMgbG9zdCBoZXJzZWxmIGluIHRoZSB3b29kcyEgU2hlIGRlc3BlcmF0ZWx5IG5lZWRzIHRvIGdldCBiYWNrIHRvIHRoZSBiYXJuIGJ1dCBoYXMgbm8gaWRlYSB3aGVyZSB0byBnby48XC9wPlxyXG5cclxuPHA+VGhlIHdvb2RzIGNhbiBiZSB0aG91Z2h0IG9mIGFzIGFuIFIgeCBDIGdyaWQgKDEgJmx0Oz0gUiAmbHQ7PSA1OyAxICZsdDs9IEMgJmx0Oz0gNSkuIEJlc3NpZSBpcyBsb2NhdGVkIGluIHRoZSBsb3dlciBsZWZ0IGNvcm5lciBhdCByb3cgMSwgY29sdW1uIDE7IHRoZSBiYXJuIGlzIGxvY2F0ZWQgaW4gdGhlIHVwcGVyIHJpZ2h0IGNvcm5lciBhdCBpbiByb3cgUiwgY29sdW1uIEMuICZuYnNwO0VhY2ggc3F1YXJlIGluIHRoZSBncmlkIGlzIGVpdGhlciBlbXB0eSAoZGVub3RlZCBieSAmIzM5Oy4mIzM5Oykgb3IgYmxvY2tlZCBieSBhIHRyZWUgKGRlbm90ZWQgYnkgJiMzOTtUJiMzOTspLiBCZXNzaWUmIzM5O3Mgc3F1YXJlIGFuZCB0aGUgYmFybiB3aWxsIGFsd2F5cyBiZSBlbXB0eS48XC9wPlxyXG5cclxuPHA+RnJvbSBhIGdpdmVuIHNxdWFyZSwgQmVzc2llIG1heSBtb3ZlIHRvIGFueSBhZGphY2VudCBzcXVhcmUgKG9uZSB0aGF0IHNoYXJlcyBhIGxvbmcgZWRnZSB3aXRoIEJlc3NpZSYjMzk7cyBjdXJyZW50IHNxdWFyZSkgYXMgbG9uZyBhcyBpdCBpcyBlbXB0eS4gQXMgQmVzc2llIGlzIHF1aXRlIGEgc21hcnQgY293LCBzaGUgbmV2ZXIgdmlzaXRzIGEgc3F1YXJlIHR3aWNlIG9uIHRoZSB3YXkgYmFjayB0byB0aGUgYmFybi48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgQmVzc2llIGNhbiB0YWtlIHRoYXQgbGVhZCBoZXIgZnJvbSBoZXIgaW5pdGlhbCBwb3NpdGlvbiBiYWNrIHRvIHRoZSBiYXJuIHdoaWxlIHZpc2l0aW5nIGF0IG1vc3QgSyBkaWZmZXJlbnQgc3F1YXJlcyAoMSAmbHQ7PSBLICZsdDs9IFIgKiBDKS48XC9wPlxyXG5cclxuPHA+Qnkgd2F5IG9mIGV4YW1wbGUsIGNvbnNpZGVyIHRoaXMgZm9yZXN0OjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgIC4uLi5cclxuICAgICAgICAuVC4uXHJcbiAgICAgICAgLi4uLlxyXG48XC9wcmU+XHJcblxyXG48cD5CZXNzaWUgaGFzIGEgbnVtYmVyIG9mIHdheXMgdG8gZ2V0IHRvIHRoZSB1cHBlciByaWdodCBjb3JuZXIsIGhlcmUgYXJlIGFsbCBzZXZlbiBvZiB0aGVtIGFuZCB0aGVpciBwYXRoIGxlbmd0aHMgKHRoZSBudW1iZXIgb2Ygc3F1YXJlcyB2aXNpdGVkKTo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgY2RlZiAgLi4uZiAgLi5lZiAgLi5naCAgY2RlaCAgY2RlaiAgLi4uZiAgXHJcbiAgICAgICAgIGJULi4gIC5ULmUgIC5UZC4gIC5UZmUgIGJUZmcgIGJUZmkgIC5UZGUgIFxyXG4gICAgICAgICBhLi4uICBhYmNkICBhYmMuICBhYmNkICBhLi4uICBhLmdoICBhYmMuICBcclxuTGVuZ3RoOiAgICA2ICAgICA2ICAgICA2ICAgICA4ICAgICA4ICAgIDEwICAgIDZcclxuPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFIsIEMsIGFuZCBLPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uUisxOiBMaW5lIGkrMSBjb250YWlucyB0aGUgQyBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyByb3cgUisxLWkgb2YgdGhlIGZvcmVzdCAod2l0aCBubyBzcGFjZXMpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBwYXRocywgdmlzaXRpbmcgYXQgbW9zdCBLIHNxdWFyZXMsIHRoYXQgQmVzc2llIGNhbiB0YWtlIHRvIGdldCBiYWNrIHRvIHRoZSBiYXJuLiBOb3RlIHRoYXQgdGhpcyBudW1iZXIgd2lsbCBhbHdheXMgZml0IGludG8gYSBzaWduZWQgMzItYml0IGludGVnZXIuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==