問題一覧 > 通常問題

No.520 An Invitation to Project Euler

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 26
作問者 : horiesiniti / テスター : tubo28
お気に入りにしたユーザー ProblemId : 1212 / 自分の提出
問題文最終更新日: 2026-06-25 02:51:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 164 (順位表) の他の問題:

Foreword

Project Euler is a competitive programming site specializing in problems of combinatorics and number theory. As befits a site with participants from all over the world, it is a great deal of fun: the solvers' forum, which only those who have answered correctly can view, is full of solutions in interesting languages you have never seen before. For example, if you do not know the J language, I recommend looking it up once. Almost all of its commands and operators are a single character, its operators use nearly every ASCII character, and writing two, three, or more operators in a row changes their meaning and order of application according to regular rules. J is a language you often see on Project Euler, and it is a fun language that changes your view of the world quite a bit when you study it.

Problem Statement

Project Euler had a problem along these lines. Let S be the set consisting of "the points placed on the 4 sides of a square so that each side is divided into n equal parts" and "the 4 vertices of the square". Choose 2 points of S and keep connecting 2 points of S, under the condition that each segment is drawn inside the quadrilateral. Keep drawing segments under the condition that they do not cross any segment drawn so far, until no more segments can be drawn. How many ways of drawing are there? Drawings that become identical under rotation or reflection are counted as distinct.

Let us modify this problem a little. On the sides of an equilateral triangle ABC, add internal division points: a1 on side a, b1 on side b, and c1 on side c. Let U be the set consisting of the internal division points and the vertices of the triangle. Choose 2 points of U and keep drawing segments, under the condition that each segment is drawn inside the triangle and does not cross any segment drawn so far, until no more segments can be drawn. How many ways of drawing are there? Given a1, b1, c1, answer modulo 1000000007.

Two examples of ways of drawing the lines for a1=2, b1=3, c1=4 are shown above. In both figures, lines have been drawn until no more lines can be drawn. When the numbers of internal division points on sides a, b, c are fixed, how many ways are there to draw lines in this manner? The triangle is placed on the Euclidean plane with vertex A at the origin, side c on the X-axis, and the Y-coordinate of point C at least 0; ways of drawing that become identical by applying rotation or reflection are regarded as different ways of drawing.

Input

$n$
$a1$ $b1$ $c1$
$\dots$
$ai$ $bi$ $ci$
$\dots$
$an$ $bn$ $cn$

0 < $n$ <= 10 The number of triangle data sets. Each data set of a triangle is given on one line. 0 < $ai$,$bi$,$ci$ <= 100
$ai$ is the number of internal division points on side a, $bi$ is the number of internal division points on side b, and $ci$ is the number of internal division points on side c.
For the given $ai$,$bi$,$ci$, let $Ansi$ be the number of ways of drawing the lines modulo 1000000007, and output each one on its own line.

Output

$Ans1$
$\dots$
$Ansi$
$\dots$
$Ansn$
Print a newline after each one.

Sample

Sample 1
Input
5
12 4 7
1 3 1
4 2 7
2 3 5
4 4 4
Output
2414171
11
2430
371
1847

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。