Rook tours

I suspect chess players are familiar with the Knight Tour (moving the knight on an empty board so that it visits every square, but once only), even if they cannot do it themselves. I also suspect fewer players are familiar with the Rook Tour (same conditions as the Knight Tour), even though everyone should be able to do this without much thought.
However, to make the study of Rook Tours more challenging, questions are phrased not in terms of 'how', but 'how much'. For example, starting in the top left corner and finishing in the bottom left corner, how many distinct rook tours are their on a 2x2 board? (In this case only 1). However as the board gets bigger, the problem gets harder.
Courtesy of the website projecteuler.net I discovered that on a 4x10 board (4 ranks and 10 files), there are 2329 distinct rook tours. However the question that they want you to solve is how many tours are their on a 4x10^12 board!
If you are interested in mathematics (especially number theory), and programming, then this is a wonderful site to visit. It contains over 200 questions designed to be solved algorithmically, and tests both mathematical knowledge, and programming ability. However do not panic if you can't solve the problem I've just given. It is problem number 237 in the list, and has only been solved by 134 people. As a comparison, Problem 1 (the sum of all positive numbers less than 1000 divisible by 3 or 5) has been solved by over 56,000 people.