Description

In mathematics, the Fibonacci numbers can be defined by the recurrence relation:

For example, if n = 3, the corresponding result will be 3.

 

Here, we want to find the reverse Fibonacci numbers defined by a similar but different recurrence relation:

For example, if G0 = 1, G1=-1, the reverse Fibonacci sequence will be like: 1,-1,2,-3,5,-8, ....

 

In this problem, given G0, G1, and n, please calculate Gn.

Input

There will be three integers(G0, G1, and n) separated by white space.

Note: ( -100000 <=G0, G1<= 100000) and (0 <= n <= 30)

Output

The nth number, Gn,  in the reverse Fibonacci number.

Note that you need to print "\n" at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Researchers found that giant panda don't move much, and when they do, it is usually for finding meals. Surprisingly, researchers have measured that pandas only expend low amount of energy per day, and due to the inadequate nutrients provided by their daily meal, they have to slow things down to avoid their energy from expending.

Now, assume that you are the panda keeper, in order to decrease the energy consumption of the panda, your boss ask you to design the shortest path from panda's shelter to meal area. However, there are some obstacles in the panda farm, you also need to bypass these obstacles.

 

The farm is a m x n matrix, and it consists five symbols:

'.' is the road that panda can walk through.

'^'  and 'o' is the tree and rock that panda can not walk through.

'S' is the the panda's shelter.

'M' is the meal area.

Your goal is to find the length of the shortest path from panda's shelter S to their meal area M.

Note that you can only move left, right, up, and down (diagonal move is not acceptable) !

 

For example, 

if the 5 x 5 farm looks like:

 . . . . S

 . o o ^ ^

 . . . . o

 ^ o ^ . o

 M . . . o

(There is a space in front of each charactor!)

 

the length of the shortest path is 14 (including M): 

 . . . . S

 . o o ^ ^

 . . . . o

 ^ o ^ . o

 M . . . o

Input

The first line contains two integers m, n, which is length and width of the farm (1 ≤ m, n ≤  1000)

The next m lines contains n characters (including '.', '^', 'o', 'S', 'M' ) which builts the aerial view of the farm

 

Output

The length of the shortest path in the farm (it is guaranteed that there is always a path from pandas' shelter S to the meal area M).

Note that the shortest path must include M, and you need to print a newline character ('\n') at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss