Легко проверить, что ни одна из записей в первых семи строках треугольника Паскаля не делится на 7:

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

1

5

10

10

5

1 1

6

15

20

15

6

1 Однако, если мы проверим первую ста строк, мы обнаружим, что только 2361 из 5050 записей не делятся на 7.

Найдите количество записей, которые не делятся на 7 в первом миллиарде (109) строк треугольника Паскаля.

Find the number of entries which are not divisible by 7 in the first one billion (10⁹) rows of Pascal's triangle.