UCV2013E  Greedy Walking
Reginald is an Ndimensional traveler who wants to return to Filipistonia's Kingdom. He has an Obsessivecompulsive disorder in the way he travels so he can only do it following particular rules:
 Every step is exactly one unit long.
 He only moves in one dimension at a time.
 He only travels along the positive direction for each dimension.
For example, when traveling on a twodimensional place. He can travel along either the X or the Y axis at any given time, but never on both at the same time. Moreover, since he only travels along the positive direction and every step is one unit long, his only possible moves are (+1, 0) and (0, +1).
As you can see, he is a Greedy Walker: once he makes a decision he assumes it is the correct and he never goes back.
Given a starting position in an Ndimensional space (x^{1}i, x^{2}i, ... ,x^{n}i) your task is to count the number of different travels he can make to position (x^{1}f, x^{2}f, ... , x^{n}f) modulo 1000000007.
Input
The input contains several test cases, each one corresponding to a single travel. Each test case consists of a single line with one integer (1 <= N <= 50) followed by two lines each one with N integers, first line will be initial position and second line will be target position.
You can assume that 0 <= x^{k}i <= x^{1}f <= 500 for all k, 1 <= k <= N and Sum(x^{k}ix^{k}f) <= 500.
The end of input is indicated by a test case with N = 0.
Output
For each travel output a single line with one integer, the number of different travels that exist from the initial position to the final position modulo 1000000007.
Example
Input: 2
2 1
5 5
4
0 0 0 0
1 2 3 4
5
1 2 3 4 5
8 5 6 4 8
5
0 0 0 0 0
100 100 100 100 100
0 Output: 35
12600
19219200
257055440
hide comments
codephilic:
20201003 11:55:33
@infinity_98 it is for n dimensional space 

Shubham Jadhav:
20200714 12:07:42
Thanks @tezu_singh for the hint :) 

infinity_98:
20200709 03:28:58
i didn,t understand the input format


tezu_singh:
20200624 10:43:13
https://www.youtube.com/watch?v=tkhyQXqVxWA&list=PLDDGPdw7e6Ag1EIznZmqXu4XX3A0cIz&index=28


Utkarsh Rastogi:
20150119 17:07:55
my 100th on spoj.. :) 

Hector Navarro:
20130729 13:05:39
@BroadSword there is only one way to get from a point to itself... 

BroadSword:
20130729 11:36:40
If initial and target positions are same..the result should be 0 or 1?


Hector Navarro:
20130725 15:44:00
@SITH: Your program generates no output... I catched an exception:


SWOOSH!!!:
20130724 06:32:24
I dont why I am getting WA again and again...@Hector could you explain to me why this is happening? Submission id 9708968 
Added by:  Hector Navarro 
Date:  20130722 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Local UCV 2013. Fernando Crema 