题目描述

豆包和奶龙进入了一个由 n 行 m 列方格组成的迷宫。豆包位于字符 D 所在的方格，奶龙位于字符 N 所在的方格。

他们每一步只能向上、下、左、右相邻的方格移动，不能进入墙壁 #。空地用 . 表示。

请计算豆包到达奶龙位置所需的最少步数，以及不同最短路线的数量。两条路线只要经过的方格序列不同，就视为不同路线。路线数量可能很大，请对 1000000007 取模。

输入格式

第一行输入两个整数 n m。

接下来 n 行，每行输入一个长度为 m 的字符串，表示迷宫。

输出格式

若豆包能够到达奶龙，输出两个整数 dist ways，分别表示最少步数和最短路线数量。

若无法到达，输出 -1 0。

样例

3 4
D...
.#..
...N

5 4

数据范围与限制

• 1 <= n, m <= 500；
• 地图中恰好有一个 D 和一个 N；
• 时间限制：2 秒；
• 空间限制：64 MiB。