← Complete problem index

PROJECT EULER · #0638

Weighted Lattice Paths

Statement only · UnsolvedOriginal problem ↗
Let Pa,b denote a path in a a×b lattice grid with following properties:
  • The path begins at (0,0) and ends at (a,b).
  • The path consists only of unit moves upwards or to the right; that is the coordinates are increasing with every move.
Denote A(Pa,b) to be the area under the path. For the example of a P4,3 path given below, the area equals 6.
crossed lines

Define G(Pa,b,k)=kA(Pa,b). Let C(a,b,k) equal the sum of G(Pa,b,k) over all valid paths in a a×b lattice grid.

You are given that

  • C(2,2,1)=6
  • C(2,2,2)=35
  • C(10,10,1)=184756
  • C(15,10,3)880419838mod1000000007
  • C(10000,10000,4)395913804mod1000000007
Calculate k=17C(10k+k,10k+k,k). Give your answer modulo 1000000007

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.