#include <stdio.h>
#include <stdlib.h>
int map[51][51] = { 0 };
int triangle(int r, int c)
{
printf("[triangle] r:%d c:%d map[r][c]:%d\t\t", r, c, map[r][c]);
if (r == c || r == 0 || c == 0)
{
printf("[return 1] 1\n");
return 1;
}
else
{
if (map[r][c] != 0)
{
printf("[return 2] r:%d c:%d map[r][c]:%d\n", r, c, map[r][c]);
return map[r][c];
}
printf("[return 3] r:%d c:%d map[r][c]:%d\n", r, c, map[r][c]);
return map[r][c] = (triangle(r - 1, c) + triangle(r - 1, c - 1)) % 100000000;
}
printf("[return 4] r:%d c:%d map[r][c]:%d\n", r, c, map[r][c]);
}
int main()
{
int r, c;
//scanf("%d %d", &r, &c);
r = 4;
c = 4;
printf("[END] %3d\n", triangle(r + (c - 2), c - 1));
return 0;
}